Strona 1 z 1
nwd z informacją o sumie
: 25 maja 2014, o 22:14
autor: Smilek22
Suma dwóch liczb naturalnych dodatnich jest równa 777. Jaka największą wartość może
przyjąć ich największy wspólny dzielnik?
Mnie wyszło, że 37. Zrobiłam to jednak nieco chaotycznie, dlatego proszę o pomoc w rozwiązaniu.
nwd z informacją o sumie
: 26 maja 2014, o 00:05
autor: mortan517
Źle. Zobacz chociażby tu:
\(\displaystyle{ x=333 \ \ y=444 \\ NWD(x,y)=111}\)
nwd z informacją o sumie
: 26 maja 2014, o 01:50
autor: gryxon
\(\displaystyle{ NWD(259,518)=259}\)
To jest największy.
Kod: Zaznacz cały
#include <iostream>
using namespace std;
int max(int a, int b){
if(a>b)return a;
else return b;
}
int nwd(int a, int b){
if(b==0)return a;
else return nwd(b,a%b);
}
int main() {
int maxi = 0;
for(int i = 1; i<=776;++i){
maxi=max(nwd(i,777-i),maxi);
}
cout << maxi;
return 0;
}
Koniec dowodu? ;p
Jak to ładnie zrobić?
nwd z informacją o sumie
: 26 maja 2014, o 07:29
autor: Hydra147
Niech \(\displaystyle{ NWD(x,y)=d}\) oraz \(\displaystyle{ x+y=777}\). Mamy zatem \(\displaystyle{ d|x}\) i \(\displaystyle{ d|y}\) czyli \(\displaystyle{ d|x+y=777}\). Największym dzielnikiem liczby 777 mniejszym od niej samej jest oczywiście 259 i jest on osiągalny np. dla \(\displaystyle{ x=518}\) oraz \(\displaystyle{ y=259}\).
nwd z informacją o sumie
: 26 maja 2014, o 10:07
autor: Smilek22
Faktycznie, pominęłam 259. Dziękuję bardzo za ładne wyjaśnienia. Zwłaszcza Hydra147.