From c6d3ba329f0e074c8b53c71a1e670f12460bd2b9 Mon Sep 17 00:00:00 2001 From: sijanec Date: Fri, 4 Dec 2020 23:26:28 +0100 Subject: mat_euler_11_narejena_naloga --- mat/euler/11/a.out | Bin 12832 -> 12840 bytes mat/euler/11/prog.c | 93 ++++++++++++++++++++++++++++++++++++++++------------ 2 files changed, 72 insertions(+), 21 deletions(-) (limited to 'mat') diff --git a/mat/euler/11/a.out b/mat/euler/11/a.out index a8b4ee3..eaae4a0 100755 Binary files a/mat/euler/11/a.out and b/mat/euler/11/a.out differ diff --git a/mat/euler/11/prog.c b/mat/euler/11/prog.c index 06cc72f..e8d6999 100644 --- a/mat/euler/11/prog.c +++ b/mat/euler/11/prog.c @@ -1,8 +1,9 @@ #include #include #include +#include #define ZACETNA_VELIKOST 128 -int ulint_array_print (unsigned long int * b, size_t a, FILE * f) { +int slint_array_print (signed long int * b, size_t a, FILE * f) { fprintf(f, "{ "); for (size_t j = 0; j < a; j++) // ob !zadnjem natisnemo še ", ". fprintf(f, "%ld%s", b[j], (j == a-1) ? "" : ", "); @@ -11,7 +12,7 @@ int ulint_array_print (unsigned long int * b, size_t a, FILE * f) { } int main (int argc, char ** argv) { if (argc != 1+1) { - fprintf(stderr, "uporaba: %s \nprimer: %s 4 < stevilka.txt\nprogram v stdin pričakuje ASCII številke, ločene z LF po vrsticah in s presledkom po stolpcih. naj se stdin konča z LF! če številke pišete na roke, začnete računanje s Ctrl+D. ker iščemo tudi po diagonalah in stolpcih se celoten input shrani v dinamično pridobljen delovni spomin.\n", argv[0], argv[0]); + fprintf(stderr, "uporaba: %s \nprimer: %s 4 < stevilka.txt\nprogram v stdin pričakuje ASCII številke, ločene z LF po vrsticah in s presledkom po stolpcih. naj se stdin konča z LF! če številke pišete na roke, začnete računanje s Ctrl+D.\n", argv[0], argv[0]); return 1; } unsigned long int n = strtoll(argv[1], NULL, 10); // Number in a row @@ -20,15 +21,19 @@ int main (int argc, char ** argv) { fprintf(stderr, "napaka! pred EOF ni bilo v stdin podatkov!\n"); return 2; } + long int zmnozek = 1; // ko množimo, uporabimo to za buffer + long long int nz = 0; size_t i = 0; // Index za loope + size_t j = 0; // index za globlJe loope + size_t k = 0; // še ena spremenljivKa size_t z = 0; // Zapisano VRSTIC! size_t r = 0; // zapisano številk pri trenutni vRstici! short int t = 0; // zapisano pri Trenutni številki, da lahko delamo strtoll - size_t velikost_v = ZACETNA_VELIKOST; size_t velikost_1 = ZACETNA_VELIKOST; // velikost ene vrstice - size_t * dolzina_vrstice = malloc(sizeof(size_t) * velikost_v); - long int ** v = malloc(sizeof(long int *)*velikost_v); // Vrstice ŠTEVILK!!! - v[0] = malloc(sizeof(long int)*velikost_1); + size_t * dolzina_vrstice = malloc(sizeof(size_t)*(n+2)); // dodamo za maxInMin + long int ** v = malloc(sizeof(long int *)*n); // zadnjih n vrstic (za (-) |/\) + for (i = 0; i < n; i++) // lahko bi samo za [0], itak je realloc po vsakem \n + v[i] = malloc(sizeof(long int)*velikost_1); size_t vel_ts = ZACETNA_VELIKOST; char * trenutna_stevilka = malloc(sizeof(char) * vel_ts); trenutna_stevilka[0] = '\0'; @@ -40,37 +45,83 @@ int main (int argc, char ** argv) { } trenutna_stevilka[t] = c; trenutna_stevilka[++t] = '\0'; - fprintf(stderr, "debug: nastavil trenutna_stevilka ob znaku '%c' na \"%s\"\n", c, trenutna_stevilka); } if (c == ' ' || c == '\n') { // ločilo if (velikost_1-3 <= r+3) { // off by one (: velikost_1 = velikost_1 * 2; - v[z] = realloc(v[z], velikost_1 * sizeof(long int)); + v[z % n] = realloc(v[z], velikost_1 * sizeof(long int)); } - v[z][r] = strtol(trenutna_stevilka, NULL, 10); - fprintf(stderr, "debug: nastavil v[%ld][%ld] iz \"%s\" na %ld.\n", z, r, trenutna_stevilka, v[z][r]); // dobro bi bilo nastaviti [0] na \0 PO tem! + v[z % n][r] = strtol(trenutna_stevilka, NULL, 10); trenutna_stevilka[0] = '\0'; r++; + if (r >= n) { // preskusimo za vodoravne faktorje + zmnozek = 1; // na prvem runnu za npr. n=4 bomo torej brali [0][1][2][3] + for (i = 0; i < n; i++) // na drugem pa bo r-1 = 1, zato [1][2][3][4] + zmnozek = zmnozek*(v[z % n][((r-1)-(n-1))+i]); // r-1 smo pravkar zapisali + if (zmnozek > nz) { + nz = zmnozek; + slint_array_print(v[z % n]+((r-1)-(n-1)), n, stdout); + fprintf(stdout, ": nove vodoravne z največjim zmnožkom %lld.\n", nz); + } + } t = 0; } if (c == '\n') { // c je ločilo - if (velikost_v-3 <= z+3) { // for good measure imamo šest vrstic več #OB1 - velikost_v = velikost_v * 2; - v = realloc(v, sizeof(long int *)*velikost_v); - dolzina_vrstice = realloc(dolzina_vrstice, sizeof(size_t) * velikost_v); - } - dolzina_vrstice[z] = r; + dolzina_vrstice[z % n] = r; velikost_1 = ZACETNA_VELIKOST; z++; - v[z] = malloc(velikost_1 * sizeof(long int)); + v[z % n] = realloc(v[z % n], velikost_1 * sizeof(long int)); + if (z >= n) { // če smo že zapisali n vrstic, lahko iščemo |\/ + dolzina_vrstice[n] = 0; // max + dolzina_vrstice[n+1] = 69694201337; // min + for (i = 0; i < n ; i++) // najprej dobimo max in min dolzino_vrstice. + if (dolzina_vrstice[i] > dolzina_vrstice[n]) + dolzina_vrstice[n] = dolzina_vrstice[i]; + if (dolzina_vrstice[i] < dolzina_vrstice[n+1]) + dolzina_vrstice[n+1] = dolzina_vrstice[i]; + zmnozek = 1; + for (i = 0; i < dolzina_vrstice[n+1]; i++) { // i-stolpec - preskušamo| + zmnozek = 1; + for (j = 0; j < n; j++) // j je vrstica + zmnozek = zmnozek*(v[j][i]); // iščemo po stolpcih + if (zmnozek > nz) { + nz = zmnozek; + slint_array_print(v[z % n]+((r-1)-(n-1)), n, stdout); + fprintf(stdout, ": nova navpična z največjim zmnožkom %lld.\n", nz); + } + } + i = 0; // stolpec + j = 0; // vrstica + k = 0; // orientacija: 0: \, 1: / + for (k = 0; k <= 1; k++) { + for (i = k ? n - 1 : 0; i < dolzina_vrstice[0]; i++) { + zmnozek = 1; + for (j = 0; j < n; j++) { + if (i >= dolzina_vrstice[j]) + goto continue_nov_stolpec_diagonala; + if (k) + zmnozek = zmnozek * v[j][i-j]; + else + zmnozek = zmnozek * v[j][i+j]; + } + if (zmnozek > nz) { + nz = zmnozek; + slint_array_print(v[z % n]+((r-1)-(n-1)), n, stdout); + fprintf(stdout, ": nove diagonale z največjim zmnožk. %lld.\n", nz); + } + continue_nov_stolpec_diagonala: + ; + } + } + } r = 0; } c = fgetc(stdin); } // sedaj samo preverimo, če se pravilno preberejo številke #DEBUG - for (i = 0; i < z; i++) { - ulint_array_print(v[i], dolzina_vrstice[i], stderr); - fprintf(stderr, "\n"); - } + // for (i = 0; i < n; i++) { + // slint_array_print(v[i], dolzina_vrstice[i], stderr); + // fprintf(stderr, "\n"); + // } return 0; } -- cgit v1.2.3