Nada

LÖSNING TILL DATALOGIÖVNING 6

STRYKORD

Tomt ord är stamfar, söner får man genom att lägga på en bokstav och kolla i ordlistan. Eftersom man inte är ute efter kortaste strykord utan tvärtom längsta är breddenförst inte så bra. Rekursiv djupetförst som går igenom hela trädet och noterar längdrekord är klart bäst, särskilt eftersom letandet i ordlistan då hela tiden går framåt! Ingen binärsökning kommer i fråga.
class Strykord                                           { 
  static String record="", listord=""                    ;
  static void pålägg(String ord)                         {
    if(ord.length()>record.length()) record=ord          ;
    for(char tkn='a'; tkn<='ö'; tkn++)                   {
      if(exists(ord+tkn)) pålägg(ord+tkn)                ;}}
  static boolean exists(String ord)                      {
    while(listord.compareTo(ord)<0) listord=Mio.GetLine();
    return listord.equals(ord)                           ;}
  public static void main(String[] args)                 {
    pålägg("")                                           ;
    System.out.println("Längsta strykord: "+record)      ;}}

//--------------------------------------------------------

Som gjort för breddenförst med heltalskö.

class Sjuor1                                             {
  static IntQueue q=new IntQueue()                       ;
  static void makesons(int tal)                          {
    if(tal==100)  System.out.println("Hundra!")          ;
    q.put(tal+7)                                         ;
    q.put(tal-7)                                         ;
    q.put(tal*7)                                         ;
    if(tal%7==0) q.put(tal/7)                            ;}
  public static void main(String[] args)                 {
    q.put(0)                                             ;
    while(!q.isEmpty()) makesons(q.get())                ;}}

class IntNode                                            {
  int element                                            ;
  IntNode next=null                                      ;}

class IntQueue                                           {
  private IntNode front=null,back=null                   ;
  public  void put(int element)                          {
    if(isEmpty()) back=front = new IntNode()             ;
    else back=back.next = new IntNode()                  ;
    back.element = element                               ;}
  public  int get()                                      {
    int element = front.element                          ;
    front=front.next                                     ;
    return element                                       ;}
  public boolean isEmpty()                               {
    return (front==null)                                 ;}}

//--------------------------------------------------------

class Node                                               {
  int tal                                                ;
  Node father                                            ;
  Node(int x, Node p)                                    {
    tal=x; father=p                                      ;}}
class Sjuor2                                             {
  static Queue q=new Queue()                             ;
  static void makesons(Node far)                         {
    if(far.tal==100)  writechain(far)                    ;
    q.put(new Node(far.tal+7,far))                       ;
    q.put(new Node(far.tal-7,far))                       ;
    q.put(new Node(far.tal*7,far))                       ;
    if(far.tal%7==0) q.put(new Node(far.tal/7,far))      ;}
  static void writechain(Node p)                         {
    System.out.print(p.tal+" ")                          ;
    if(p.father!=null) writechain(p.father)              ;}
  public static void main(String[] args)                 {
    q.put(new Node(0,null))                              ;
    while(!q.isEmpty()) makesons((Node)q.get())          ;}}

//--------------------------------------------------------

LABYRINT

Problemträdet har (0,0) som stamfar och tillåtna grannpunkter ger söner. I en dumsonsmatris markerar man vilka punkter man redan besökt. Breddenförst fungerar då bra och ger kortaste vägen.