Strona główna > Ch. Tw. > Chińskie twierdzenie o resztach

Chińskie twierdzenie o resztach

25 Sierpień 2011 Dodaj komentarz Go to comments
//Chinskie twierdzenie o resztach
//Rozwiazywanie ukladow
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void WprowadzRowania(int ile, int c[], int n[])
{
  printf("Podaj rowania modularne w postaci:\n");
  printf("x = c (mod n):\n");
  for(int i=0;i<ile;i++)
  {
     printf("Rowanie %d: \n", (i+1));
     printf("Podaj c:  ");scanf("%d", &c[i]);
     printf("Podaj n:  ");scanf("%d", &n[i]);
     printf("\n\n");
  }
}

int Algorytm_euklidesa(int a, int b)
{
    if(a>0 && b>0)
    {  int r=0;
       do{ r=a%b;
           a=b;
           b=r;
         }while(b!=0);
    return a;
    }
    return -1;
}

int Rozszerzony_Algorytm_Euklidesa(int a, int b)
{
    if(a>0 && b>0)
    {
       int a0=a, b0=b;
       int p=1, q=0, r=0, s=1;
       int c,new_r, new_s,quot;
       while (b!=0)
       {  c=a%b;
          quot =(int)floor(a/b);
          a=b;
          b=c;
          new_r=p-quot*r;
          new_s=q-quot*s;
          p=r; q=s;
          r=new_r;
          s=new_s;
       }
    printf("NWD(%d,%d)=%d*%d + %d*%d ", a0, b0, a0, p, b0, q);
    printf(" = %d\n", (a0*p)+(b0*q));
    return p;
    }
    else{ printf("Error!");
    return -1;}
 }

int SprawdzNWD(int ile, int n[])
{
    int i=0,True=1;
    while(True==1 && i<ile)
    {
       for(int j=i+1;j<ile;j++)
       True=Algorytm_euklidesa(n[i],n[j]);
       i++;
    }
    return True;
}

void run()
{
  int ile;
  printf("Chinskie tw o resztach\n");
  printf("Ile rownan ma zawierac uklad?\n");
  scanf("%d", &ile);
  int c[ile],n[ile];
  WprowadzRowania(ile,c,n);
  if(SprawdzNWD(ile,n)==1)
  {
     int x=0,N[ile], X[ile];
     for(int i=0;i<ile;i++)
     N[0]*=n[i];
     for(int i=0;i<ile;i++)
     N[i+1]=N[0]/n[i];
     for(int i=0;i<ile;i++)
     {
        X[i]=Rozszerzony_Algorytm_Euklidesa(N[i+1],n[i]);
        if(X[i]<0) X[i]=X[i]+n[i];
     }
     for(int i=0; i<ile;i++)
     x+=c[i]*X[i]*N[i+1];
     x=x%N[0];
     printf("\nRozwiazanie ukladu = %d\n", x);
  }
  else printf("Nie istnieje rozwiazanie\n");
}

int main(int argc, char *argv[])
{
  run();
  system("PAUSE");
  return 0;
}
  1. 6 Wrzesień 2011 o 1:29 pm

    Hmm;) Swietne

  1. No trackbacks yet.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: