1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
package lastfirst;
public class LastFirst {
public static int sol[] = {-1, -1, -1, -1, -1};
public static int pos = 0;
public static boolean trouve(int sol[], int j) {
for (int i = 0; i < sol.length; i++) {
if (sol[i] == j) {
return true;
}
}
return false;
}
public static void affiche(String[] t, int[] sol) {
for (int j = 0; j < t.length && sol[j] != -1; j++) {
System.out.print(t[sol[j]]);
}
}
public static boolean ok(String t[], int sol[], int j) {
if (pos == 0) {
return true;
} else {
String ch1 = t[sol[pos - 1]];
String ch2 = t[j];
return ch1.charAt(ch1.length() - 1) == ch2.charAt(0);
}
}
public static boolean solve(String[] t) {
int i;
if (pos == t.length)// la solution est trouvé et tous les mots sont utilisés
{
return true;
}
for (i = 0; i < t.length; i++) {
if (trouve(sol, i) == false)// si le mot n'est pas encorre utilisé
{
if (ok(t, sol, i) == true)// si le mot et compatible avec la solution
{
sol[pos] = i;// en le place dans le tableau solution
affiche(t, sol);
System.out.println("");
pos++;
if (solve(t) == true) {
return true;// appel recursive
}
pos--;
sol[pos] = -1;
}
}
}
return false;// si pas des solution trouvés
}
public static void main(String[] args) {
// String t[] = {"358", "123", "874" , "826","638"};
String t[] = {"358", "123", "573", "826", "638"};
//la solution existe :123 358 826 638 874
System.out.print(solve(t));
}
} |
Partager