Algorytm Euklidesa

Question

1. Napisać program znajdujący największy wspólny dzielnik dodatnich liczb całkowitych algorytmem Euklidesa. Proszę pomyśleć o zaimplementowaniu w pętli for().

Potrzebuję zeby ktoś wykonal to zadanie w jezyku C, najprosciej jak sie da bez uzyca tablic, wskaźników itp. Gdyż mam problem z utworzeniem pętli for

Comments

To już nawet nie kwestia tego. że prosisz o gotowca, co na tym forum jest nieetyczne i niedozwolone. Rzecz w tym, że ten algorytm został zaimplementowany setki tysięcy razy. Wystarczy wpisać w Google i wybrać sobie ten, który Ci się spodoba. Jak szafkę z Ikei, tylko tu masz łatwiej, bo nie musisz nic sam składać.

Lenistwo, które reprezentujesz, to już wyższy poziom ignorancji :-)

---

Szukałam po wielu stronach i z uzyciem pętli for nie znalazłam nic sensowneg wszedzie jest jedynie pętla while

---

@Ala123456, proszę nie prosić o gotowe rozwiązania problemów na forum. Rozumiem, że może być Ci ciężko wykonać niektóre zadania, ale zrzucając odpowiedzialność za ich wykonanie na inne osoby na pewno sobie nie ułatwisz zadania w przyszłości. Na twoim miejscu spodziewałbym się, że jeżeli nie radzisz sobie z obecnymi problemami (które są całkiem proste do rozwiązania, jeżeli się tylko przyłoży do tego), to nie poradzisz sobie także z następnymi. Na twoim miejscu zabrałbym się na poważnie do pracy, aby zrozumieć i nauczyć się programowania, albo po prostu zrezygnował z obecnego kierunku edukacji.

Jako, że to nie pierwsze pytanie tego typu (prośba o rozwiązanie problemu) otrzymujesz ostrzeżenie. Kolejne takie pytania będą skutkowały zablokowaniem konta. Nie podchodź do tego ostrzeżenia negatywnie, to nie po to by Cię zdołować. Przemyśl sprawę.

A co do tego, że jest pętla while, to jaki problem? Jeżeli wiesz jak działa pętla for, to nie powinnaś mieć żadnego problemu z przerobieniem pętli for na while). Pokaż może swój obecny kod (bo pomóc możemy, oczywiście, ale pisać gotowych rozwiązań już nie), to mogę pomóc. 

---

# include <stdio.h>
int main ()
{
    int a,b;
    printf("Podaj dwie liczby calkowite wieksze od 0:\n");
    printf("a = ");
    scanf("%i", &a);
    printf("b = ");
    scanf("%i", &b);
    if (a<=0 | b<=0){
    printf("Podano nieprawidlowe wartosci.");}
    else {
    printf("NWD(%i,%i)=",a,b);}
    while(a!=b){
    if (a>b){
    a=a-b;}
    else {
    b=b-a;}}
    printf("%i\n",a);
    return 0;
}

To jest przy użyciu while ale nie mam pojecia jak przerobić to na petle for

---

#include <stdio.h>
int main()
{
    int a, b;
    printf("Podaj dwie liczby calkowite wieksze od 0:\n");
    printf("a = ");
    scanf("%i", &a);
    printf("b = ");
    scanf("%i", &b);
    if (a <= 0 | b <= 0) {
        printf("Podano nieprawidlowe wartosci.");
    }
    else {
        printf("NWD(%i,%i)=", a, b);
    }
    for (;a != b;) {
        if (a > b) {
            a = a - b;
        }
        else {
            b = b - a;
        }
    }
    printf("%i\n", a);
    return 0;
} 


A to jest poprawnie?

 

---

No masz, akurat zacząłem tworzyć identyczny kod. 

Tak, to jest poprawnie (przynajmniej na takie mi wygląda). W razie czego, w odpowiedzi mojej masz wyjaśnienie.

Answer 1

Poprawiłem trochę twój kod, aby wyglądał estetyczniej. Dzięki temu będzie Ci (i nam) dużo łatwiej go czytać oraz znajdywać ewentualne błędy.

# include <stdio.h>
int main()
{
    int a, b;
    printf("Podaj dwie liczby calkowite wieksze od 0:\n");
    
    printf("a = ");
    scanf("%i", &a);
    
    printf("b = ");
    scanf("%i", &b);
    
    if (a <= 0 | b <= 0)
    {
        printf("Podano nieprawidlowe wartosci.");
    }
    else
    {
        printf("NWD(%i, %i) = ", a, b);
    }

    for (; a != b;)
    {
        if (a > b)
        {
            a = a - b;
        }
        else
        {
            b = b - a;
        }
    }

    printf("%i\n", a);
    return 0;
}

Zamiana pętli while na pętlę for nie kosztowała zbyt dużo wysiłku. Po prostu wystarczy wiedzieć, jak pętla for działa. Aby to Ci wytłumaczyć, posłużę się przykładem.

for (int i = 0; i < 5; ++i) {
    //Jakiś kod...
}

W nawiasie mamy trzy części. Użycie każdej z nich jest opcjonalne! Pierwsza z nich to kod, który wykonuje się przed wykonaniem się samej pętli. Wykonuje się on tylko raz. Druga część to warunek, który jest sprawdzany za każdym razem przed wykonaniem następnego obiegu pętli (w tym pierwszego). Trzecia część to instrukcja, która wykonuje się po każdym obiegu pętli (a przed sprawdzeniem warunku). A więc kod ten można zapisać równie dobrze tak:

int i = 0;
while (i < 5) {
    // Jakiś kod
    ++i;
}

A jako, że możemy pominąć wymienione przeze mnie części, wystarczyło zamienić linię

while (a != b)

na

for (; a!=b;)

I tyle. 

Comments

Dziękuję :D

---

Plain text?! 

---

@Eryk Andrzejewski, wiem, że pomogłeś użytkownikowi z jego kodem i temat rozwiązany, ale myślę, że warto wspomnieć również o lepszej wersji algorytmu Euklidesa: 

int NWD(int a, int b)
{
    int pom;
    
    while(b!=0)
    {
		pom = b;
		b = a%b;
		a = pom;	
	}
	
    return a;
}

A zmieniona przeze mnie wersja wyglądałaby mniej więcej tak: 

int NWD(int a, int b)
{
    
    for( int pom = b; pom != 0; pom = b)
    {
		b = a%b;
		a = pom;	
	}
	
    return a;
}

Teraz to choć trochę przypomina klasyczną wersję pętli for, a nie taką nikczemną podmiankę za while :-P

Oczywiście oba rozwiązania są poprawne według treści zadania. Moje wymaga jednak troszkę więcej zrozumienia samego algorytmu. 

---

@Eryk Andrzejewski,

W if pod:

printf("Podano nieprawidlowe wartosci.");

trzeba by jeszcze dodać:

return 0;

W przeciwnym razie (przy podaniu nieprawidłowych wartości) program będzie się zawieszał.

Najlepszym rozwiązaniem byłaby możliwość ponownego wprowadzania danych, ale to już wymaga większej przeróbki.

 

---

Jeszcze krócej bez "ciała" pętli for.. 

#include <iostream>

int myGCD(int n1, int n2) {

    for(;n1 != n2; n1 > n2 ? n1 -= n2 : n2 -= n1);

    return n1;
}

int main() {
    int n1, n2;

    std::cout << "Enter two numbers separated by space: ";

    std::cin >> n1 >> n2;

    std::cout << "GCD " << n1 << " and "
        << n2 << " -> " << myGCD(n1, n2) << '\n';
}

 

---

Dobre!  Bardzo mocne!  Jeden z "wynalazków" Zachodu!  Tylko, że na skróty, nie "po szkolnemu", nie dydaktyczny, i brak zabezpieczenia strumienia wejściowego.

Musisz dokładnie opisać składnię pętli for, ponieważ tam przerzuciłeś ciało., wygląda dziwacznie, podejrzanie (i że średnikiem na końcu).

---

Nie wiem czy nie dydaktyczny. Pokazuje wyraźnie że for(..) ma sekcje w których można wprowadzać wyrażenia wykonywane wielokrotnie a część "inkrementacjna" (bo tak tego uczą), wcale inkrementacją/dekrementacją może się nie zajmować bo wymagania stawiane w języku brzmią: "uruchamiaj przy każdym przebiegu pętli".

Co do zabezpieczenia strumienia wejściowego... jesteś pewien że nie zaciemniło by to przykładu? Bo ja jestem pewien że tak. Poboczne pytania do czego służy ignore i numerical_limits na strumieniu nie są sednem problemu.

Ostatnia rzecz która jest istotna. Przykład podałem już _po_ umieszczeniu "śmiertelnie dydaktycznych poprawnych i zgodnych z wymaganiami UE" :>

Niemniej jednak cieszę się że Ci się podoba.

---

Myślę, że największym beneficjentem jest Ala12345, którą na początku znalazła się w dramatycznej sytuacji.

---

Beginer, dzięki za zwrócenie uwagi. W każdym razie ja kod autorki tylko uczytelniłem, nie zwróciłem uwagi na błąd.