M3 - Programació estructurada / Continguts UF1: Esquema de cerca

Esquema de cerca

Fonamentalment l’esquema de cerca ens permetrà resoldre problemes en què busquem un element concret dins d’una seqüència. A diferència de l’esquema de recorregut, en que es visiten i tracten tots els elements de la seqüència, l’esquema de cerca :

només recorre la seqüència fins a trobar l’element desitjat

La forma genèrica de l’esquema de cerca és la següent:

 accedir al primer element
 inicialitzar tractament
 Mentre no últim element i no element trobat fer
   obtenir següent element
 fmentre
 tractament final

Veurem a continuació alguns exemples en els quals s’ha aplicat l’esquema de cerca per a escriure el programa. És un bon exercici intentar identificar quina és la seqüència que s’està tractant en cada programa i com s’han refinat les accions genèriques de l’esquema de recorregut en cada cas concret

Exemple 4: Números de Fibonacci

Dissenyar un programa que determini si entre els 1000 primers números de Fibonacci hi ha algun que acabi en 9. En cas de que el número existeixi, escriurem el primer que trobem per pantalla, en cas contrari escriurem el número –1. Els números de Fibonacci estan definits de la següent forma:

fib1= 0

fib2 = 1

fibn = fibn-1 + fibn-2 per a n > 2

public class Fibonacci {
 public static void main(String[] args) {
   int i, act, sig, sig2;
   act = 0;
   sig = 1;
   i = 1;
   while (i <= 1000 && (act % 10) != 9) {
     sig2 = act + sig;
     act = sig;
     sig = sig2;
     i = i + 1;
   }
   if ((act % 10) == 9) {
   System.out.println(act);
   } else {
         System.out.println(-1);
     }
 }
}

Exemple 5: Apareix la lletra ‘a’ ?

Dissenyar un programa per a detectar si en una frase llegida per teclat i acabada en punt existeix o no alguna lletra ‘a’

public class ApareixA {
 public static void main(String[] args) {
   char c;
   Scanner lector = new Scanner(System.in);
   c = lector.next().charAt(0);
   while (c != '.' && c != 'a') {
     c = lector.next().charAt(0);
   }
   if (c == 'a') {
     System.out.println("Sï apareix");
   } else {
         System.out.println("No apareix");
     }
 }
}