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

Posty: 12
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: 26 maja 2014, o 00:05 
Użytkownik
Avatar użytkownika

Posty: 3401
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 01: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 07:29 
Użytkownik

Posty: 259
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 10:07 
Użytkownik

Posty: 12
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
 Dwie kartki, liczba naturalna n, liczby o sumie cyfr =10  szysza94  4
 Wykazać zbieżność w sumie dwóch metryk  Poszukujaca  1
 Oblicz, ile początkowych wyrazów ciągu daje w sumie 627  robert19m  1
 Gry dwuosobowe o sumie zero  adamkus12  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl