INTRODUZIONE ALLA PROGRAMMAZIONE CON IL CALCOLATORE ANTROPOMORFO

IL CALCOLATORE ANTROPOMORFO

Il calcolatore antropomorfo consiste di un omino racchiuso in una cabina che riceve istruzioni e dati attraverso due strisce di carta continue illimitate che entrano ed escono dalla cabina attraverso due feritoie (dette input ed output).

L'omino può fare solamente le seguenti cose (cioè queste sono le sue istruzioni):

riga

IL PROBLEMA

Costruire un itinerario che colleghi due città su una rete stradale.

riga

L'ALGORITMO (IL PROGRAMMA)

Input/output

INPUT (cosa dare al programma)
città di partenza
città di arrivo
rete stradale
OUTPUT (cosa ritornerà il programma)
elenco delle città che costituiscono l'itinerario, se un itinerario esiste, niente altrimenti

Rappresentazione dell'informazione

CITTÀ
sequenza di caratteri
ITINERARIO
sequenza di città
RETE STRADALE
sequenza delle coppie di città tra cui esiste un tronco autostradale
riga

Algoritmo 1

Idea: costruire man mano itinerari sempre più lunghi che partono dalla città di partenza, controllando ogni volta se ne esiste uno che che arriva nella meta.

leggere sulla striscia di input la città di partenza e copiarla sul foglietto A

leggere sulla striscia di input la città di arrivo e copiarla sul foglietto B

leggere sulla striscia di input la rete stradale tronco dopo tronco 
e copiarla sul foglietto RETE
 
scrivere sul foglietto ITINERARI gli itinerari di lunghezza 1 che partono 
da A

mentre su ITINERARI non c'è scritto un itinerario che finisce in B fare
    ( prendere un foglietto bianco e chiamarlo AUSILIARE
      per ogni itinerario  c1, ...cn  scritto su ITINERARI
          prendere un foglietto bianco e chiamarlo CITTA 
          scrivere su CITTA tutte le città raggiungibili da cn
          per ogni città c scritta su CITTA
               scrivere su AUSILIARE  c1,...,cn,c 
      cancellare ITINERARI
      ricopiare AUSILIARE su ITINERARI
     )
scrivere sulla striscia di output il primo itinerario in ITINERARI 
che finisce in B
riga

Algoritmo 2

Idea: non costruire itinerari che contengono cicli; il nuovo algoritmo e presentato di seguito, in rosso le correzioni.

leggere sulla striscia di input la città di partenza e copiarla sul foglietto A

leggere sulla striscia di input la città di arrivo e copiarla sul foglietto B

leggere sulla striscia di input la rete stradale tronco dopo tronco 
e copiarla sul foglietto RETE
 
scrivere sul foglietto ITINERARI gli itinerari di lunghezza 1 che partono 
da A (non ci saranno cicli)

mentre su ITINERARI non c'è scritto un itinerario che finisce in B fare
    ( prendere un foglietto bianco e chiamarlo AUSILIARE
      per ogni itinerario  c1, ...cn  scritto su ITINERARI
          prendere un foglietto bianco e chiamarlo CITTA 
          scrivere su CITTA tutte le città raggiungibili da  cn
          che sono differenti da  c1, ..., cn
          per ogni città  c  scritta su CITTA
               scrivere su AUSILIARE  c1,...,cn,c 
      se c'è scritto qualcosa su AUSILIARE,  allora
          ( cancellare ITINERARI
            ricopiare AUSILIARE su ITINERARI
          )
      altrimenti scrivere sull'ouput "non ci sono itinerari"
     )
scrivere sulla striscia di output il primo itinerario in ITINERARI 
che finisce in B

riga

ESERCIZI

  1. Scrivere un programma per il calcolatore antropomorfo per trovare tutti gli itinerari esistenti tra due città.
  2. Scrivere un programma per il calcolatore antropomorfo per trovare l'itinerario più corto tra due città si assuma che la rete stradale sia corredata dalle lunghezze dei tronchi.