C++ pętle, NWD i prawdopodobienstwo

Question

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int i, j, c, d;
    int p=0;
    for(i=1; i<=10000; i++)
    {
        for(j=1; j<=10000; j++)
        {
            if (j>i) swap(i,j);
            else
            {
                while(j!=0)
                {
                    c=i%j;
                    i=j;
                    j=c;
                    d=i;

                }
            }
            if (d>sqrt(i+j)) p++;
        }
    }
    cout<<p/100000000;

    return 0;
}

Napisz program, który obliczy prawdopodobieństwo, że największy wspólny dzielnik dwóch liczb 
        z zakresu od 1 do 10000 włącznie jest liczbą większą niż zaokrąglony w dół pierwiastek z sumy
        tych liczb.

Może mi ktoś powiedzieć co tutaj robię źle?

Answer 1

Pierwsze podejście to podziel kod na funkcjen i inizjalizuj zmienne w miejscu ich pierwszego użycia. Zacznij od napisania algorytmu eludesa jako osobna funkcja.

Comments

#include <iostream>
#include <cmath>

int dzielnik (int a, int b)
{
    if (b>a)
    {
        int tmp=b;
        b=a;
        a=tmp;
    }
    else
    {
        while(b!=0)
        {
            int c=a%b;
            a=b;
            b=c;
        }
        return a;
    }

}

int pierw (int a, int b)
{
    return sqrt(a+b);
}

using namespace std;

int main()
{
    int p;
    for (int i=1; i<=10000; i++)
    {
        for (int j=0; j<=10000; j++)
        {
            dzielnik (i,j);
            pierw(i,j);
            if (dzielnik(i,j)>pierw(i,j));
            p++;
        }
    }
    cout<<p/10000;
    return 0;
}

Zmodyfikowalam w ten sposob i dalej jest zle :(

---

Nie nadajesz wartości początkowej zmiennej p i w linii 41 wkradł ci się średnik którego nie powinno tam być. Algorytm Euklidesa można poprawić (powinien działać, ale można to zrobić szybszej).

---

Usunelam srednik i napisalam wartosc poczatkowa p=0 i nie wyskakuje mi zaden blad ale jak uruchamiam to kompilator nic mi nie wyswietla.

---

Używasz IDE, czy komplikujesz w konsoli? Jeśli w konsoli to po komplikacji trzeba uruchomić program. Ja nie widzę w kodzie nic ci mogło by być przyczyną nie prawidłowego działania. Widzę że można coś poprawić, ale to co widzę to jest kosmetyka, a nie błąd krytyczny.

---

Normalnie uruchamiam w CodeBlocks'ie, inne programy mi działają w ten sposób :(

---

#include <stdio.h>

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

double prawdopodobienstwo(int a, int b) {
  int result = 0;
  int nwd2 = 0;
  for (int i = a, j = a; i <= b; ++i) {
    if (i > j) {
      i = a;
      ++j;
    }
    nwd2 = nwd(j, i);
    nwd2 = nwd2 * nwd2;
    if (nwd2 > (j + i)) {
      ++result;
      // printf("%d > %d + %d\n", nwd2, j, i);
    }
  }
  return result / ((b - a) * (b - a) / 2.0);
}

int main() {
  printf("Prawdopodobieństwo = %lf\n", prawdopodobienstwo(1, 1e4));

  return 0;
}

To jest moja implementacja w C. Ten kod powinien być szybszy noż twój, a i tak potrzebował prawie pół minuty żeby to obliczyć. Jedyne co testowałem to ile czasu potrzebuje na obliczenie, a wynik wydaje się być sensowny, ale nie jestem pewny czy na pewno jest poprawny. Jestem w stanie powiedzieć że twój kod prawdopodobnie będzie potrzebować ponad minuty żeby podać wynik. Twój kod sprawdza każdą parę liczb 2 razy i korzysta z pierwiastkowania które jest wolniejsze od mnożenia. Ja sprawdzam czy suma liczb jest mniejsza od kwadratu NWD, co jest szybszą operacją i każdą parę cyfr sprawdzam raz. Widzę jeszcze inne optymalizacje które można zastosować. Na przykład można pominąć wszystkie sprawdzania dla których i*i<i+j, bo nwd jest zawsze mniejsze równe.
PS.zwróć uwagę że prawdopodobieństwo musi być mnisze równe 1.

---

Ajj, rzeczywiście, wszystko działa mi jak należy, tylko jak kompilator nie uruchamiał mi programu od razu to myślałam, że coś nie działa, a trzeba było tylko czasu żeby to uruchomić, dziękuję ci bardzo 

---

Program uruchamia się od razu, ale potrzebuje czasu żeby wydrukować wynik. Tak w roli ścisłości.