szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 25 maja 2014, o 21:14 
Użytkownik

Posty: 11
Lokalizacja: Toruń
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.
Góra
Mężczyzna Offline
PostNapisane: 25 maja 2014, o 23:05 
Użytkownik
Avatar użytkownika

Posty: 3367
Lokalizacja: Krk
Źle. Zobacz chociażby tu:
x=333 \ \ y=444 \\ NWD(x,y)=111
Góra
Mężczyzna Offline
PostNapisane: 26 maja 2014, o 00:50 
Użytkownik

Posty: 314
Lokalizacja: Puławy
NWD(259,518)=259

To jest największy.

Kod:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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ć?
Góra
Mężczyzna Offline
PostNapisane: 26 maja 2014, o 06:29 
Użytkownik

Posty: 254
Lokalizacja: Polska
Niech NWD(x,y)=d oraz x+y=777. Mamy zatem d|x i d|y czyli d|x+y=777. Największym dzielnikiem liczby 777 mniejszym od niej samej jest oczywiście 259 i jest on osiągalny np. dla x=518 oraz y=259.
Góra
Kobieta Offline
PostNapisane: 26 maja 2014, o 09:07 
Użytkownik

Posty: 11
Lokalizacja: Toruń
Faktycznie, pominęłam 259. Dziękuję bardzo za ładne wyjaśnienia. Zwłaszcza Hydra147.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność liczby całkowitej o sumie cyfr  ala75607  1
 Wykaż nierówność dla trzech liczb o sumie 1.  piotrekkazek  5
 Dowód twierdznia o sumie  somemat  2
 Iloczyn dwóch liczb o określonej sumie  PoweredDragon  3
 twierdzenie o maksimum iloczynu przy stałej sumie  szymek12  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl