Wątek przeniesiony 2015-04-13 23:06 z C/C++ przez ŁF.

NWD wszystkich możliwych par zbioru [1, ... , n]

0

Cześć, bardzo proszę o pomoc. Chcę napisać program zliczający pary względnie pierwszych liczb wśród wszystkich możliwych dwuelementowych zbiorów zbioru n elementowego. Problem jest w pętli zagnieżdżonej: chciałabym, żeby program dla n=(np)4 liczył najpierw NWD 1,1; 1,2; 1,3; 1,4; a póżniej 2,1; 2,2; 2,3; itd...

Pomysł jest taki:

#include<iostream>
#include<cstdlib>
using namespace std;

int NWD(int a, int b)
{
    while(a!=b)
       if(a>b)
           a-=b; 
       else
           b-=a;
    return a;
}


int main()
{
    int n,c=1,i=0;
    cout << "podaj n: " << endl; cin >> n;

    while (c<=n)
    {
        while ((c+i)<=n)
        {
            NWD (c,c+i);
            cout << NWD (c,c+i) << endl;
            i++;
        }
        c++;
    }
    return 0;

Problem polega na tym, że program liczy i wypluwa dobrze dla 1,1; 1,2; 1,3 itd..., ale nie przeskakuje na 2,1; 2,2; itd... Czy może lepiej to zrobić tablicami i pętlą for? Proszę o pomoc.

1

Użyj dwóch pętli for i tablicy dwuwymiarowej

0

Teoretycznie jest to zadanie na poziomie bez tablic. Spróbuję je zrobić tak jak mówisz, ale ciekawa jestem rozwiązania tymi najbardziej elementarnymi metodami, czy ktoś ma pomysł? Program ma jeszcze zliczyć te NWD==1.

1

Uzyj szybszego algorytmu NWD:

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

Ten Twoj jest bardzo wolny w niektorych przypadkach. (np. NWD(1, 1000000) wykona 1000000 operacji)

0

Dziękuję, tak zrobiłam. Program nadal wykonuje tylko tę środkową pętlę, nie przechodzi w ogóle do zewnętrznej, tak jakby nie widział tego 'c++'... Gdzie jest błąd?

0

Zamien cout << NWD (c,c+i) << endl; na cout << "NWD ("<< c << "," << c+i ") = " << NWD (c,c+i) << endl;,

odpal dla N=5 i powiedz co wyswietla i czego nie ma

0

Nie wiedzieć czemu zrozumiał zamienione polecenie jako string... Ale po poprawie dla N=5 wyświetla:

NWD (1,1) = 1
NWD (1,2) = 1
NWD (1,3) = 1
NWD (1,4) = 1
NWD (1,5) = 1

i nic więcej.

dodanie znacznika <code class="none"> - @furious programming

0

Problem rozwiązany, więc wklejam cały, poprawny kod, być może ktoś kiedyś się nim zainspiruje. Obyło się bez tablic, ale za to nie bez forów. Pozdrawiam!

 #include<iostream>
#include<cstdlib>
using namespace std;

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


int main()
{
    double n, wynik=0;
    cout << "podaj n: " << endl; cin >> n;
    for(int i=1;i<=n;++i)
       for(int j=1;j<=n;++j)
          if(NWD(i,j)==1)
            ++wynik;
    double prawdopodobienstwo = wynik/(n*n);
    cout << "prawdopodobienstwo wynosi: " << prawdopodobienstwo;
    system("Pause");
    return 0;
0

można inaczej
sito Eratostenesa do "n" i jeszcze jedna prosta, sumująca pętelka.

1 użytkowników online, w tym zalogowanych: 0, gości: 1