Diferència entre revisions de la pàgina «M3 - Programació estructurada / Continguts UF1: Esquema de cerca»
(Es crea la pàgina amb «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...».) |
|||
Línia 1: | Línia 1: | ||
− | 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 | + | 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 : |
− | 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 | + | :::'''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: | La forma genèrica de l’esquema de cerca és la següent: | ||
+ | <pre> | ||
accedir al primer element | accedir al primer element | ||
inicialitzar tractament | inicialitzar tractament | ||
− | Mentre no últim element i no element trobat fer | + | Mentre no últim element i no element trobat fer |
− | + | obtenir següent element | |
− | fmentre | + | fmentre |
tractament final | tractament final | ||
+ | </pre> | ||
+ | |||
+ | 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: | |
− | |||
− | |||
− | de | ||
− | + | :fib1= 0 | |
− | + | :fib2 = 1 | |
− | + | :fibn = fibn-1 + fibn-2 per a n > 2 | |
− | + | <source lang="java"> | |
− | |||
− | fib1= 0 | ||
− | fib2 = 1 | ||
− | fibn = fibn-1 + fibn-2 per a n > 2 | ||
public class Fibonacci { | public class Fibonacci { | ||
public static void main(String[] args) { | 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); | |
− | + | } | |
} | } | ||
} | } | ||
+ | </source> | ||
− | Exemple 5: Apareix la lletra ‘a’ ? | + | '''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’ | + | Dissenyar un programa per a detectar si en una frase llegida per teclat i acabada en punt existeix o no alguna lletra ‘a’ |
+ | <source lang="java"> | ||
public class ApareixA { | public class ApareixA { | ||
public static void main(String[] args) { | 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"); | |
− | + | } | |
} | } | ||
} | } | ||
+ | </source> |
Revisió de 12:33, 19 oct 2020
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");
}
}
}