drmichko@obelix : 01/06/16 _ _ _ _ _ __ _| | __ _ ___ _ __(_) |_| |__ _ __ ___ (_) __ _ _ _ ___ / _` | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \| |/ _` | | | |/ _ \ | (_| | | (_| | (_) | | | | |_| | | | | | | | | | (_| | |_| | __/ \__,_|_|\__, |\___/|_| |_|\__|_| |_|_| |_| |_|_|\__, |\__,_|\___| |___/ |_| --- travail personnel : requis utilisation du compte : libre commandes réseaux : interdites permission HOMEDIR : drwx------ Ne pas changer les noms de fichiers Utiliser des lignes de moins de 72 caracteres. Tous les programmes, fichiers etc... devront etre places dans le repertoire d'examen : /home/drmichko/exam-tp-I51-2016-drmichko Vous validerez votre travail par la commande : /home/partage/pl/validexam -m I51 --- ====================================================================== 1. Quicksort ====================================================================== Ecrire un programme trichaine.c en langage C pour obtenir une commande trichaine.exe qui prend une chaine en argument sur la ligne de commande, trie les carcateres dans l'ordre ascii : prompt> ./trichaine.exe QUICKSORT CIKOQRSTU Le programme demandé doit obligatoirement utilisé la fonction qsort de la bibliotheque glibc. :: cat trichaine.c #include #include #include static int cmp(const void *p1, const void *p2) { return *(char *) p1 - *(char*) p2; } int main(int argc, char *argv[]) { qsort(argv[1], strlen(argv[1]), 1, cmp); puts(argv[1]); return 0; } ====================================================================== 2. Euclide ====================================================================== On note I(a,b) le nombre d'iteration de l'algorithme d'Euclide pour calculer le PGCD de a et b. Pour un entier a, on note f(a) la moyenne des I(a,b) quand b satisfait : PGCD(a,b) = 1 et 1 < b < a [ a ] Ecrire un programme en langage C qui prend un entier en argument sur la ligne de commande, calcule et affiche f(a) f( 512 ) = typedef unsigned long long ullong; int pgcd(ullong a, ullong b, ullong * g) { int cpt = 0; ullong r; while (b > 0) { r = a % b; a = b; b = r; cpt++; } *g = a; return cpt; } int main(int argc, char *argv[]) { ullong a, b, g; int i, t, n = 0; a = atoi(argv[1]); for (b = 1; b < a; b++) { i = pgcd(a, b, &g); if (g == 1) { t += i; n++; } } printf("f(%llu) = %.4f\n", a, (float) t / n); return 0; } [ b ] Faire la representation graphique iter.png pour a variant dans l'intervalle 1 < a < 1024. :: for(( x=1; x<1024;x+=10)) do ./a.out $x; done | grep -v A | tr -cd '[0-9 \n\.]' > iter.dat done :: gnuplot gnuplot> plot 'iter.dat' w l , log(x)*0.87 [ c ] Determiner empiriquement une approximation de f de la forme A * ln( x ) :: gcc -Wall iter.c -lm :: ./a.out 1234567 f(1234567) = 12.2869 A = 0.8760 A = 0.87... La valeur theorique est : > bc -l bc 1.06.95 scale=10; pi=4*a(1) 12*l(2)/pi^2 .8427659134 ====================================================================== 3. PGCD étendu ====================================================================== Ecrire un programme pgcd.c qui prend deux entiers a et b sur la ligne de commande puis trace le calcul du pgcd etendu de a et b ====================================================================== 4. Backtracking ====================================================================== On considere une variante du puzzle des n reines dans laquelle une reine controle les memes cases que dans le jeu classique, sauf que les cases du bord de l'echiquier ne sont pas controlees sur par des diagonales : x . x . x . . . x . . . . x x x . . . x x x . . x x Q x x x x x Q x x x . x x x . . . x x x . . x . x . x . . . x . x . . . . . . x . . . . . . classique variante Dans cette variante, une Reine qui n'est pas sur le bord de l'echiquier controle 4 cases de moins que dans le jeu classique. [ a ] Ecrire un progamme reine.c qui calcule le nombre R(n) de facons de poser n reine sur un échiquier n x n. #include #include int nbsol = 0; int admis(int i, int j, int c[], int limite) { int k; for (k = 0; k < i; k++) { if (c[k] == j) return 0; } if (j == 0) return 1; // modification if (j == limite) return 1; // par rapport if (i == limite) return 1; // au puzzle classique for (k = 0; k < i; k++) { if (abs(c[k] - j) == i - k) return 0; } return 1; } void Gauss(int c[], int p, int n) { int i; if (p == n) { nbsol++; return; } for (i = 0; i < n; i++) { if (admis(p, i, c, n - 1)) { c[p] = i; Gauss(c, p + 1, n); } } } int main(int argc, char *argv[]) { int col[max], n = atoi( argv[1]); Gauss(col, 0, n ); printf("R( %d ) = %d\n", n, nbsol); return 0; } [ b ] Préciser le nombre de solutions n 1 2 3 4 5 6 R(n) 1 2 4 10 26 84 [ c ] Estimer le temps de calcul. T( n ) = [ d ] Pour quelles valeurs de n, le programme pourrait calculer R(n) en moins de 1 jour ? --- drmichko@obelix