[C++] problem z równaniem diofantycznym

0

Witam, próbuje napisać program, który będzie sprawdzał liczbę rozwiązań takiego równania:

a+b2+c3+d^4=n

Najpierw należy podać ilość działań (ilość n), później wartość liczby n.
Oto co udało mi się napisać

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
int t;
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int sprawdzwynik(int one,int two,int three,int four, int wynik){
   int okej = static_cast<int>(one + pow(two,2) + pow(three,3) + pow(four,4));
   if(okej == wynik){return 1;}
   if(okej != wynik){return 0;}
}


int main()
{
scanf("%d", &t);
int n[t][2];
//petla od wyzerowania tablicy ilosci rozwiazan
for(int m = 0; m<t; m++){
        n[m][1] = 0;
        }
//petla pobierajaca liczby
for(int i = 0; i<t; i++){
        scanf("%d", &n[i][0]);
//petla sprawdzajaca a
for(int t = 0; i<n[i][0]; t++){
a = t;
n[i][1] += sprawdzwynik(a,b,c,d,n[i][0]);
//petla sprawdzajaca b^2
for(int y = 0; y<(pow((n[i][0]),1/2)); y++){
b = y;
n[i][1] += sprawdzwynik(a,b,c,d,n[i][0]);
//petla sprawdzajaca c^3
for(int u = 0; u<(pow((n[i][0]),1/3)); u++){
c = u;
n[i][1] += sprawdzwynik(a,b,c,d,n[i][0]);
//petla sprawdzajaca d^4
for(int r = 0; r<(pow((n[i][0]),1/4)); r++){
d = r;
n[i][1] += sprawdzwynik(a,b,c,d,n[i][0]);
}
}
}
}

}

for(int z = 0; z<t; z++){
printf("%d",n[z][1]); }
}

Po odpaleniu nawet gdy za n dam 1, program zacina się i zżera 100% procesora. Wie ktoś co jest tego powodem?

0

hs.spoj :)

0

jep ;-)
wystarczyło poprawić literówkę w pętli, inaczej użyć powa i dodać kilka rzeczy, już zrobione
Ma ktoś pomysł na optymalizację? Przekraczam czas ponad dwukrotnie ;oo

0

powiem ci ,że też dzisiaj zrobiłem to zadanie ale moje wygląda krócej i prościej :P u ciebie strasznie dużo liczenia w ogóle przeszło ?
a i co do twojego rozwiązania nie musisz magazynować obliczeń a pod koniec zwrócić wyników możesz to zrobić częściowo czyli obliczyć zwrócić wynik potem znów pobrać itd.

0

Wynik jest dobry, tylko na ich maszynie za dlugo sie wykonuje (ponad 2x):
1 0.0 : 2.0 przekroczono limit czasu
(1.71s : 1.0s)
2 0.0 : 2.0 przekroczono limit czasu
(4.98s : 2.0s)
3 0.0 : 2.0 przekroczono limit czasu
(6.87s : 3.0s)
4 0.0 : 2.0 przekroczono limit czasu
(8.96s : 4.0s)
5 0.0 : 2.0 przekroczono limit czasu
(4.98s : 2.0s)

kod:

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
int t, a, b, c, d, g, y, u, r;


int main()
{
scanf("%d", &t);
int n[t][2];
//petla od wyzerowania tablicy ilosci rozwiazan
for(int m = 0; m<t; m++){
        n[m][1] = 0;
        }
//petla pobierajaca liczby
for(int i = 0; i<t; i++){
        scanf("%d", &n[i][0]);
        a = 0; b = 0; c = 0; d = 0;
//petla sprawdzajaca a
for(g = 0; g <= (n[i][0]); g++){
a = g;
int sukces = static_cast<int>(a + pow(b,2) + pow(c,3) + pow(d,4));
if(n[i][0] == sukces){n[i][1]++;}
if(n[i][0] == 0){break;}
//petla sprawdzajaca b^2
for(y = 0; y <= (pow((n[i][0]),0.5)+1); y++){
b = y;
sukces = static_cast<int>(a + pow(b,2) + pow(c,3) + pow(d,4));
if(n[i][0] == sukces){n[i][1]++;}
//petla sprawdzajaca c^3
for(u = 0; u <= (pow((n[i][0]),0.34)+1); u++){
c = u;
sukces = static_cast<int>(a + pow(b,2) + pow(c,3) + pow(d,4));
if(n[i][0] == sukces){n[i][1]++;}
//petla sprawdzajaca d^4
for(r = 0; r <= (pow((n[i][0]),0.25)+1); r++){
d = r;
sukces = static_cast<int>(a + pow(b,2) + pow(c,3) + pow(d,4));
if(n[i][0] == sukces){n[i][1]++;}
}
}
}
}
}



for(int z = 0; z<t; z++){
printf("%d \n",n[z][1]); }
}

Może dasz jakąś wskazówkę? To moje to takie typowe brute force ^^

btw. Ta kolejność to chyba nie ma znaczenia bo i tak ładnie pokazało dla każdej liczby

0

no chłopie się dziwisz :D tyle pętli tyle potęg itp szok :) mój program ma 2 pętle tylko i 2 potęgi i 2 pierwiastki i jak pisałem gdybyś nie magazynował obliczeń itp to byś dużo zaoszczędził :)
a co do wskazówki możesz zauważyć ,że pętla np dla 4 potęgi nie musi przelatywać do n tylko do pow(n,(1/4)) czyli pierwiastka z n 4 stopnia :)
a 2 wskazówka A w ogóle nie musisz liczyć bo dla każdego B będzie tylko 1 A ja u siebie pominąłem a

0

pierwiastki są -> "r <= (pow((n[i][0]),0.25" ,
Z tym omijaniem A to nie bardzo rozumiem, przecież może być 0->n kombinacji z A :ooo

0

jeżeli d4 + c3 + b^2 <= n to istnieje A a więc A nie będziesz musiał liczyć

0

podaj link do zadania.

0

a ja mysle, ze jest na to prostry wzor...

 
Rozwiązanie równania Diofantycznego może być bardzo trudne. Ale niektóre równania, jak na przykład a+b2+c3+d4=n, mają <b>trywialne</b> rozwiązanie dla każdego n
0

Moim zdaniem lepiej to podzielić na 3 problemy:

  1. ile rozwiązań d^4<=n
  2. ile rozwiązań c3<=m (m=n - d4)
  3. ile rozwiązań b2<=o (o=n - d4- c^3)

Z 1. masz jedną pętle for, z 2 kolejną, a z 3 konkretny wzór.
Czyli do policzenia potrzebne są jedynie dwie pętle, które dadzą złożoność obliczeniową: o(n^{\frac 7{12}})

0

Marek trafiłeś w 10 :P good rozwiązanie :)

0
MarekR22 napisał(a)

Moim zdaniem lepiej to podzielić na 3 problemy:

  1. ile rozwiązań d^4<=n
  2. ile rozwiązań c3<=m (m=n - d4)
  3. ile rozwiązań b2<=o (o=n - d4- c^3)

Z 1. masz jedną pętle for, z 2 kolejną, a z 3 konkretny wzór.
Czyli do policzenia potrzebne są jedynie dwie pętle, które dadzą złożoność obliczeniową: o(n^{\frac 7{12}})

Też miałem problem z tym zadaniem i nie do końca rozumiem, czy... rozwiązaniem będzie w tym wypadku suma tych trzech rozwiązań + maksymalne możliwe a?

0
pawegio napisał(a)
  • maksymalne możliwe a?

Maksymalne a wynosi n, dla b,c,d=0

sprawdzalem łopatologicznie:

for(D=0 ; D<=tabP[2] ; D++)
                {
                      tabD[D]<=n ? i++ : 0;
                }
                for(C=0 ; C<=tabP[1] ; C++)
                {
                      tabC[C]<=n-tabP[2] ? i++ : 0;
                }
                for(B=0 ; B<=tabP[0] ; B++)
                {
                      tabB[B]<=n-tabP[2]-tabP[1] ? i++ : 0;
                }
	 	 	    
                for(int A=0 ; A<=n ; A++)
                {
                      A<=n-tabP[2]-tabP[1]-tabP[2] ? i++ : 0;
                }

Wrong answer.

0

zadanie nie jest trudne. Zwracam jednak uwagę wszystkim mądralom, że to jest zadanie konkursowe, więc nie wolno podawać rozwiązania.

Zresztą na większości forów jest wyraźny zakaz zakładania tematów związanych z trwającymi konkursami! Tu taki zakaz nie istnieje, ale moim zdaniem ten wątek i tak się posunął za daleko.

0

masz rację. Proponuję zamknąć.

0

ale co poradzisz ,że ludzie piszą ja nie pisałem swojego rozwiązania bo bym był zdyskwalifikowany

0

Mógłby ktoś podrzucić jakieś testy wraz z odpowiedziami?

0
  1. w informatyce test zawsze zawierają w sobie odpowiedź
  2. pisanie testów na własne potrzeby dla tego problemu jest częścią konkursu.
  3. takie testy mogą wyglądać tak:
int liczbaRozwiazanDla(int n); // twoja metoda rozwiązująca problem
// implementacja jest twoim problemem

const struct {
      int n;
      int wynik;
} daneTestowe[] = {
     {0,1},
     {1,4},
     {2,7},
     {4,9},
     {5,11}
/* itd itp*/
};

const int testCount = sizeof(daneTestowe)/sizeof(daneTestowe[0]);

void main {
    int failed = 0;
    for(int i=0; i<testCount ; ++i) {
         int n = daneTestowe[i].n;
         int wynikoczekiwany = daneTestowe[i].wynik;;
         int wynik = liczbaRozwiazanDla(n);
         if(wynikoczekiwany !=wynik) {
               cerr << "Test FAIL for n = " << n << endl;
               cerr << "\treturned value is: " << wynik  << endl;
               cerr << "\texpected value is: " << wynikoczekiwany << endl;
               failed++;
         }
    }
    if(failed>0) {
        cerr << failed << " test FAILED" << endl;
    } else {
        cout << "all test PASSED" << endl;
    }
}
0
qwe napisał(a)

Mógłby ktoś podrzucić jakieś testy wraz z odpowiedziami?

123 -178
178 -261
111 -164
123 -1511
100000 -189462
12131 -20083
2031234 -4810269
782 -1155

wejscie-wyjscie

0

Macie przykładowe testy:
Dla N=0 - 1
Dla N=1 - 4
Dla N=2 - 7
Dla N=4 - 9
Dla N=5 - 11

Dla N=8 - 13
Dla N=9 - 16
Dla N=10 - 19
Dla N=11 - 20
Dla N=12 - 21

Dla N=15 - 22
Dla N=16 - 24
Dla N=17 - 29
Dla N=18 - 32

Dla N=33 - 55
Dla N=34 - 56
Dla N=35 - 56
Dla N=36 - 58

Dla N=39 - 62
Dla N=40 - 63

Dla N=51 - 77
Dla N=52 - 80
Dla N=53 - 82
Dla N=54 - 82

Dla N=65 - 95
Dla N=66 - 98
Dla N=67 - 98
Dla N=68 - 100

Dla N=79 - 109
Dla N=80 - 112
Dla N=81 - 117
Dla N=82 - 121

Dla N=92 - 139
Dla N=93 - 140
Dla N=94 - 140
Dla N=95 - 140
Dla N=96 - 141
Dla N=97 - 143
Dla N=98 - 146

Dla N=105 - 155
Dla N=106 - 156

Dla N=120 - 174
Dla N=121 - 175

Dla N=124 - 181

Dla N=131 - 197
Dla N=132 - 197
Dla N=133 - 198
Dla N=134 - 199
Dla N=135 - 200

Dla N=146 - 222
Dla N=147 - 222

Dla N=160 - 235
Dla N=161 - 239
Dla N=162 - 241
Dla N=163 - 242
Dla N=164 - 244

Dla N=171 - 254
Dla N=172 - 256
Dla N=173 - 256
Dla N=174 - 257

Dla N=192 - 275
Dla N=193 - 276
Dla N=194 - 277

Dla N=199 - 283
Dla N=200 - 283
Dla N=201 - 284
Dla N=202 - 285

Dla N=220 - 309
Dla N=221 - 310
Dla N=222 - 312

Dla N=225 - 319
Dla N=226 - 325
Dla N=227 - 326

Dla N=237 - 338
Dla N=238 - 338

Dla N=254 - 359
Dla N=255 - 360
Dla N=256 - 362
Dla N=257 - 367

Dla N=269 - 388
Dla N=270 - 390
Dla N=271 - 390
Dla N=272 - 392
Dla N=273 - 395
Dla N=274 - 395

Dla N=282 - 406
Dla N=283 - 408
Dla N=284 - 410
Dla N=285 - 412
Dla N=286 - 412
Dla N=287 - 414

Dla N=297 - 431

Dla N=304 - 439
Dla N=305 - 442

Dla N=310 - 450
Dla N=311 - 450

Dla N=324 - 472
Dla N=325 - 474
Dla N=326 - 475

Dla N=331 - 478
Dla N=332 - 482
Dla N=333 - 485

Dla N=335 - 485

Dla N=349 - 509
Dla N=350 - 511
Dla N=351 - 513

Dla N=360 - 527
Dla N=361 - 530
Dla N=362 - 532

Dla N=370 - 548
Dla N=371 - 549

Dla N=376 - 552

Dla N=393 - 579
Dla N=394 - 579
Dla N=395 - 580
Dla N=396 - 580
Dla N=397 - 584

Dla N=410 - 606
Dla N=411 - 606
Dla N=412 - 607
Dla N=413 - 609

Dla N=425 - 624

Dla N=431 - 634
Dla N=432 - 635
Dla N=433 - 637

Dla N=447 - 655

Dla N=457 - 666
Dla N=458 - 667
Dla N=459 - 668
Dla N=460 - 670

Dla N=474 - 689
Dla N=475 - 689

Dla N=483 - 699
Dla N=484 - 701
Dla N=485 - 703

Dla N=500 - 720
Dla N=501 - 721
Dla N=502 - 723

Dla N=507 - 730
Dla N=508 - 734

Dla N=522 - 755

Dla N=533 - 773
Dla N=534 - 773
Dla N=535 - 773
Dla N=536 - 774

Dla N=551 - 799
Dla N=552 - 799
Dla N=553 - 804
Dla N=554 - 804
Dla N=555 - 805
Dla N=556 - 807
Dla N=557 - 808

Dla N=579 - 835
Dla N=580 - 836
Dla N=581 - 837
Dla N=582 - 838

Dla N=595 - 857
Dla N=596 - 857
Dla N=597 - 858
Dla N=598 - 858
Dla N=599 - 860

Dla N=609 - 876
Dla N=610 - 878
Dla N=611 - 879

Dla N=619 - 891
Dla N=620 - 892
Dla N=621 - 893
Dla N=622 - 893

Dla N=635 - 921
Dla N=636 - 921

Dla N=644 - 935
Dla N=645 - 935
Dla N=646 - 935
Dla N=647 - 936
Dla N=648 - 938

Dla N=661 - 965
Dla N=662 - 966
Dla N=663 - 967

Dla N=671 - 977
Dla N=672 - 978
Dla N=673 - 979
Dla N=690 - 1007
Dla N=691 - 1007
Dla N=692 - 1008
Dla N=693 - 1011

Dla N=701 - 1024
Dla N=702 - 1025
Dla N=703 - 1026
Dla N=704 - 1028
Dla N=705 - 1033

Dla N=722 - 1052
Dla N=723 - 1052
Dla N=728 - 1058
Dla N=729 - 1060
Dla N=730 - 1064
Dla N=731 - 1066

Dla N=741 - 1085
Dla N=742 - 1086
Dla N=743 - 1088
Dla N=744 - 1089
Dla N=745 - 1093
Dla N=746 - 1098

Dla N=756 - 1117
Dla N=757 - 1119
Dla N=758 - 1120
Dla N=759 - 1122

Dla N=766 - 1132
Dla N=767 - 1133
Dla N=768 - 1136
Dla N=769 - 1139

Dla N=780 - 1151
Dla N=781 - 1154
Dla N=782 - 1155
Dla N=783 - 1155

Dla N=786 - 1168
Dla N=787 - 1168
Dla N=788 - 1168
Dla N=789 - 1170
Dla N=790 - 1170

Dla N=801 - 1192
Dla N=802 - 1195
Dla N=803 - 1195

Dla N=807 - 1197
Dla N=808 - 1199
Dla N=809 - 1201

1 użytkowników online, w tym zalogowanych: 0, gości: 1