#include // Version itérative int pgcd_iter(int a, int b) { while (b) { int t = a; a = b; b = t % b; } return a; } // Alternative recursive int pgcd_rec(int a, int b) { if (b) return pgcd_rec(b, a%b); else return a; } void print_array(int l, const int t[]) // le tableau t ne sera pas modifié { int i = 0; while (i < l) { printf("%3d ", t[i]); // %d suffit, mais pour pascal c'est plus joli avec i = i + 1; } printf("\n"); } void fill_even(int n, int t[]) { int i = 0; while (i < n) { t[i] = 2*i; i = i + 1; } } int sum(int len, const int array[]) { int i = 0, sum = 0; while (i < len) { sum = sum + array[i]; i = i + 1; } return sum; } int dot_product(int len, const int v1[], const int v2[]) { int i = 0, sum = 0; while (i < len) { sum = sum + v1[i]*v2[i]; i = i + 1; } return sum; } void array_sum(int len, const int v1[], const int v2[], int res[]) { int i = 0; while (i < len) { res[i] = v1[i] + v2[i]; i = i + 1; } } void pascal_line(int n, int tab[]) { int i = n - 1; tab[i] = 1; while (i > 1) { i = i - 1; tab[i] = tab[i - 1] + tab[i]; } } void pascal(int n) { int i = 0; int tab[n]; while (i < n) { i = i + 1; pascal_line(i, tab); print_array(i, tab); } } int is_sorted(int l, const int tab[]) { int i = 1; while (i < l) { if (tab[i] < tab[i - 1]) return 0; i = i + 1; } return 1; } int in_array(int k, int l, const int tab[]) { int i = 0; while (i < l) { if (tab[i] == k) return 1; i = i + 1; } return 0; } int in_sorted_array(int k, int l, const int tab[]) { int start = 0; int stop = l - 1; while (start <= stop) { int mid = (stop + start) / 2; if (tab[mid] > k) stop = mid - 1; else if (tab[mid] < k) start = mid + 1; else return 1; } return 0; } void test_member(int len, const int tab[], const int tab2[]) { // Ce test est un peu pourri (d'un point de vue test) int i = 0; while (i < len) { printf("%d => %d (est il pair ?)\n", tab[i], in_array(tab[i], len, tab2)); printf("%d => %d (est il pair ?)\n\n", tab[i], in_sorted_array(tab[i], len, tab2)); printf("%d => %d (est il dans ?)\n", tab[i], in_array(tab[i], len, tab)); printf("%d => %d (est il dans ?)\n\n", tab[i], in_sorted_array(tab[i], len, tab)); i = i + 1; } } int main(int argc, char* argv[]) { int tab[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int tab2[9]; int tab3[9]; print_array(9, tab); printf("Somme: %d\n", sum(9, tab)); fill_even(9, tab2); print_array(9, tab2); printf("Somme: %d\n", sum(9, tab2)); printf("Produit scalaire: %d\n", dot_product(9, tab, tab2)); array_sum(9, tab, tab2, tab3); printf("Somme membre a membre: "); print_array(9, tab3); test_member(9, tab, tab2); pascal(10); return 0; } // Les bonus int member_sorted_r_int(int k, int start, int stop, const int tab[]) { if (start > stop) // Les curseurs se sont croisés return 0; int mid = (stop + start) / 2; if (tab[mid] > k) return member_sorted_r_int(k, start, mid - 1, tab); else if (tab[mid] < k) return member_sorted_r_int(k, mid + 1, stop, tab); return 1; } int member_sorted_r(int k, int l, const int tab[]) { return member_sorted_r_int(k, 0, l - 1, tab); } void bubble_sort(int l, int tab[]) { int done; do { done = 1; for (int i = 0; i < l - 1; i = i + 1) if (tab[i] > tab[i + 1]) { int tmp = tab[i]; // echanger tab[i] <=> tab[i + 1] tab[i] = tab[i + 1]; tab[i + 1] = tmp; done = 0; // on a fait une permutation, on a donc pas fini } } while (!done); } void eratostene(int len, int tab[]) { int i = 0; int access = 0; while (i < len) { while (!tab[i]) { // On cherche le premier non nul i = i + 1; access = access + 1; } int j = 1; while (j*i < len) { tab[j * i] = 0; j = j + 1; access = access + 1; } } printf("%d\t%d\n", len, access); }