matura 2019 liczby i ich dzielniki

Question

Dzień dobry

Proszę o wyjaśnienie i podpowiedź. Robię zadanie 4.3, dwa pozostałe podpunkty umiem. 

Porównujemy jedną liczbę z drugą, ustalamy ich NWD, który okazuje się być większy od 1. Potem porównujemy drugą liczbę z trzecią i tu już są cztery przypadki:

a) druga i trzecia są względnie pierwsze;

b) ich NWD jest taki sam jak między pierwszą liczbą a drugą np. ciąg liczb to 14 35 i 63;

c) ich wspólny NWD jest większy niż pomiędzy pierwszą a drugą liczbą np. ciąg liczb to 12 24 48;

d) ich wspólny NWD jest mniejszy niż pomiędzy pierwszą a drugą liczbą np. ciąg liczb to 48 24 12.

I to się ciągnie przez 500 liczb. Nie wiem, jak zapisać if na ostatni warunek. Dla drugiego jest to if ( nwd ( liczby[1], liczby[2]) == nwd ( liczby[2], liczby[3]) ), dla trzeciego if ( liczby[3]%nwd(liczby[1], liczby[2]) == 0 ). A dla trzeciego? Czy ja muszę ten nwd rozbijać na dzielniki? Poza tym pogubiłam się w zmiennych, bo dość dużo ich trzeba.

Powinnam dokończyć kod tym tokiem myślenia, czy może istnieje dużo prostszy sposób? Zdaję sobie sprawę z tego [url]https://mateuszrus.pl/matura-rozszerzona-z-informatyki/[/url], ale nie znam użytych funkcji w tym kodzie. Nieznane funkcje wolę stosować na znanych mi problemach. Większa część kodu jest do podpunktów 1 i 2, które mi wyszły. Kod się kompiluje, ale zwraca zły wynik. Tak jak mówię, moje zmienne są źle.

#include <iostream>
#include <fstream>

using namespace std;

///robimy tablice z potegami 3. potegi 3 mniejsze od 100k koncza sie na potegi 10.
///porownujemy czy sie zgadza

long int silnia ( int n)
{
    if (n==0) return 1;
    else return n*silnia(n-1);
}
///robie iteracyjnie, wiec program skompiluje sie troche dluzej, ale zajmie mniej pamieci.
long int nwd( long int x, long int y)
{
    if ( x>y )
    {
        x=x-y;
    }
    else if ( y>x )
    {
        y=y-x;
    }
    else
        return x;

}
void rozklad( long int n )
{
    long tab[30]={0};

}


int main()
{
    ifstream dane;
    ofstream wynik;
    dane.open("liczby.txt");
    wynik.open("wyniki4.txt");

    long int trojki[11],liczba,ad1=0;
    trojki[0]=1;

    for ( int i=1; i<11; i++ )
    {
        trojki[i]=3*trojki[i-1];

    }

    short int r;
    long int suma=0;

    for ( int i=0; i<500; i++)
    {
        dane>>liczba;

        for ( int zi=0; zi<11; zi++)
        {
            if ( liczba == trojki[zi] )
            {
                ad1++;
                break;
            }
        }


    }
    dane.seekg(0);

    wynik << "Ad 1. " <<endl  << ad1 << endl;
    wynik << "Ad 2. " << "\n";

    long int liczby[500];
    for ( int i=0; i<500; i++ )
    {
        dane>>liczba;

        liczby[i]=liczba;
         while (liczba>0)
        {
          r=liczba%10;
          suma=suma+silnia(r);

         liczba=liczba/10;
        }
        if ( suma==liczby[i])
        {
            wynik << liczby[i] << "\n";
        }
        suma=0;
    }

    long int dzielnik,dlugosc=1,gdziePoczatek=1,szukanaLiczba=0,maks=1;


    for ( int i=1; i<499; i++)
    {
        dzielnik=nwd( liczby[i-1], liczby[i]);

        if ( dzielnik=nwd(liczby[i], liczby[i+1]) && dzielnik>1 )
        {
            dlugosc++;
        }
        else if ( liczby[i+1]%dzielnik==0 )

        {
            dlugosc++;
        }
        else
        {
            if ( dlugosc>maks)
            {
                maks=dlugosc;
                szukanaLiczba=gdziePoczatek;

            }
            gdziePoczatek=i;
            dlugosc=1;

        }

    }
wynik << "Ad 3. " << endl << szukanaLiczba << endl << maks << endl << dzielnik;

    dane.close();
    wynik.close();
    return 0;
}

 

Answer 1

Twoje rozwiązanie jest chyba trochę zbyt zachłanne i raczej będzie dawało złe wyniki. Tutaj nie trzeba wymyślać niczego szybkiego ani pomysłowego, a można sobie nawet pozwolić na rozwiązanie w O(n^2).

Najprościej to zrobić tak, że dla każdej liczby z wejścia, będziesz zakładała, że jest ona tą pierwszą liczbą ciągu, którego szukasz. Powiedzmy, że ustaliłaś sobie, że tą pierwszą liczbą jest liczba na pozycji i. Wtedy wystarczy, że będziesz kolejno dodawała do tego ciągu liczby na pozycjach i+1, i+2, ..., n, dopóki ich NWD jest większy od 1. Bo trzeba zauważyć, że jak do istniejącego ciągu dodasz jakąś nową liczbę, to NWD wynikowe ciągu może albo zmaleć albo nie zmienić się.

Także to co musisz napisać to dwie zagnieżdzone pętle. Pierwsza pętla przechodzi po wszystkich liczbach i traktuje je jako pierwszy element ciągu wynikowego, a druga pętla dodaje kolejne liczby po tej wybranej tak długo, aż ich NWD > 1.

Comments

Fakt, coś było nie tak z moim programem i dane liczby się nie wczytały, ale ok. Skopiowałam kod do całego programu (bo jest jeszcze kod z całym zadaniem 4) i tu działa, ale wynik jest zły według klucza. I teraz mam dylemat. Zastanawiać się nad kodem, czy uznać, że skoro działa to działa...

---

A to dziwne, bo uruchomiłem ten kod u siebie i wynik jest taki sam jak w kluczu

---

Przepraszam, że Cię męczę, ale ten kod zwraca Ci dobry wynik?

#include <iostream>
#include <fstream>

using namespace std;

///robimy tablice z potegami 3. potegi 3 mniejsze od 100k koncza sie na potegi 10.
///porownujemy czy sie zgadza

long int silnia ( int n)
{
    if (n==0) return 1;
    else return n*silnia(n-1);
}

long int nwd( long int x, long int y)
{
    if ( x>y )
    {
        x=x-y;
    }
    else if ( y>x )
    {
        y=y-x;
    }
    else
        return x;

}



int main()
{
    ifstream dane;
    ofstream wynik;
    dane.open("liczby.txt");
    wynik.open("wyniki4.txt");

    long int trojki[11],liczba,ad1=0;
    trojki[0]=1;

    for ( int i=1; i<11; i++ )
    {
        trojki[i]=3*trojki[i-1];

    }

    short int r;
    long int suma=0;

    for ( int i=0; i<500; i++)
    {
        dane>>liczba;

        for ( int zi=0; zi<11; zi++)
        {
            if ( liczba == trojki[zi] )
            {
                ad1++;
                break;
            }
        }


    }
    dane.seekg(0);

    wynik << "Ad 1. " <<endl  << ad1 << endl;
    wynik << "Ad 2. " << "\n";

    long int liczby[500];
    for ( int i=0; i<500; i++ )
    {
        dane>>liczba;

        liczby[i]=liczba;
         while (liczba>0)
        {
          r=liczba%10;
          suma=suma+silnia(r);

         liczba=liczba/10;
        }
        if ( suma==liczby[i])
        {
            wynik << liczby[i] << "\n";
        }
        suma=0;
    }
int j=0,dlugosc=0; long int aktualne_nwd, pierwsza, szukane_nwd, dzielnik=0;
   for ( int i=0; i<500; i++)
   {
       j=i;
       aktualne_nwd=liczby[i];

       while  ( (j<499) && ( nwd(aktualne_nwd, liczby[j+1]) >1) )
       {
           dzielnik=nwd(aktualne_nwd, liczby[j+1]);

           j++;
       }
       if( (j-i+1) >dlugosc)
       {
           dlugosc=j-i+1;
           pierwsza=liczby[i];
           szukane_nwd=dzielnik;
       }
   }

wynik << "Ad 3. " << endl << "pierwsza liczba ciagu: " << pierwsza << endl << "dlugosc ciagu: " << dlugosc << endl;
wynik << "najwiekszy wspolny dzielnik: " << dzielnik;


    dane.close();
    wynik.close();
    return 0;
}

 

---

Masz kilka błędów w tym kodzie. Po pierwsze funkcja nwd nie jest poprawna. Po drugie zapomniałaś o tej linijce:

aktualne_nwd = nwd(aktualne_nwd, liczby[j+1]);

A po trzecie powinnaś wypisywać zmienną szukane_nwd, a nie dzielnik

---

Ok dziękuję bardzo teraz działa, pozdrawiam i miłego dnia.