Witam,
Dopiero zaczynam rozwiązywać algorytmy i niestety już mam problem, z którym nie mogę sobie poradzić. Chodzi o sprawdzenie czy jedna z dwóch liczb jest wielokrotnością drugiej. Żeby nie było tak łatwo, nie można tu stosować funkcji mod. Można tylko dodawać odejmować mnożyć i dzielić.
0
0
lol? To odejmuj od większej tą mniejszą w pętli aż ci się zrobi mniejsza lub równa 0. Jak równa 0 to mamy wielokrotność. Jak nie to nie.
Błagam, powiedz mi że jesteś w 2 klasie podstawówki. Bo twój problem jest mniej więcej na tym poziomie...
0
Shalom napisał(a):
lol? To odejmuj od większej tą mniejszą w pętli aż ci się zrobi mniejsza lub równa 0. Jak równa 0 to mamy wielokrotność. Jak nie to nie.
Ten tok rozumowania jest błędny! Wywali się na unsigned int! Należy dodawać (zaczynając od 0) tę mniejszą, aż wynik dodawania się zrówna lub będzie większy niż ta większa! Jak równy większej to mamy wielokrotność. Jak nie to nie.
BP NMSP ;-)
0
Należy dodawać (zaczynając od 0) tę mniejszą, aż wynik dodawania się zrówna lub będzie większy niż ta większa!
Ten tok rozumowania jest błędny! Wywali się np. gdy mniejsza = -1, a wieksza = 5.
0
Ten tok rozumowania jest błędny! Należy "mnożyć" przez kolejne potęgi dwójki, aż będziemy znać najwyższy bit wyniku, potem sprawdzać kolejne bity i zmniejszać dzielną, po dojściu do najniższego bitu jeśli dzielna == 0, to nasz hipotetyczny dzielnik faktycznie jest dzielnikiem. zaraz rzucę kodem w c#.
oto jest:
private int pow2(int n) { int m = 1; for (int i = 0; i < n; i++) m *= 2; return m; }
int a = 171, b = 13, c = 0; // a = b * c, c nieznane
int m = 0, n = 1;
if (a == 0 || b == 0) throw new ArithmeticException();
if (a < 0) a = -a;
if (b < 0) b = -b;
if (b > a) { c = a; a = b; b = c; } // a ma być większe od b
while (b * n < a) { n = n * 2; m++; } // m = najwyższy bit + 1
for (int i = m - 1; i >= 0; i--)
{
int p = pow2(i);
int r = b * p;
if (r <= a) { a -= r; c += p; }
}
// jeśli tutaj a == 0, to a dzieli b lub b dzieli a bez reszty; c zawiera wynik dzielenia
uprzedzając komentarze - tak, dla liczb bliskich 2^31 kod wyleci w kosmos, jednak chodzi tu o zasadę działania, a nie detale. zamiast mnożenia przez 2 oczywiście powinno być przesunięcie bitowe, ale nie ma info o tym w warunkach zadania.
teraz dzieci uruchomcie sobie swoje naiwne algorytmy dla a=2^30 i b=3 i porównajcie z tym.
0
bogdans napisał(a):
Należy dodawać (zaczynając od 0) tę mniejszą, aż wynik dodawania się zrówna lub będzie większy niż ta większa!
Ten tok rozumowania jest błędny! Wywali się np. gdy mniejsza = -1, a wieksza = 5.
E tam, i tak wywali się na unsigned int :)
1
Ten tok rozumowania jest błędny!
Zakładając że to co autor napisał to nie pomyłka:
Można tylko dodawać odejmować mnożyć i dzielić.
return a / b * b == a; // tylko trzeba pamietać, żeby |a| >= |b|
Tyle...
0
@msm ten tok rozumowania jest błędny, bo to podchwytliwe jest! Dzieląc za pomocą komputera automatycznie wykonujesz też modulo! :P