002 Algoritmul lui Euclid extins

[•SpiderMan]

Stii cum se spune: un exemplu te poate ajuta, dar in acelasi timp "deruta". Sunt probleme in care exemplul este un fel de "caz particular" , iar tu tratezi fara sa vrei acel caz, iar de restul uiti, si asa s-a dus problema de rapa 

[•crissty82]

Salut

Ma chinui de o juma de ora....
Asta e codul meu pt care primesc 0 puncte
Ce nu e bine?

Cod:

#include<iostream.h>
#include <fstream.h>
int eucl(int a, int b)
{
    if(a==b) return a;
    if(a>b)
           return eucl(a-b,b);
    else
        return eucl(a,b-a);
}
int main()
{
    int a,b,minim;
    ifstream fisin("euclid.in");
    fisin>>a;fisin>>b;
    fisin.close();
    ofstream fisout("euclid.out");
    fisout<<eucl(a,b);
  
   
   fisout.close();
}

Foloseste [ code ] ... [/ code ] cand postezi cod.

[•best4him]

Cod:

// algoritmul lui euclid.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
#include<fstream>
ifstream f("euclid2.in.txt");
ofstream g("euclid2.out.txt");
int cmmdc(int a, int b)
{  int r;
    r = a % b;
      while(r != 0)
       {
         a = b;
         b = r;
         r = a % b;
      }
	  return b;
}

int _tmain(int argc, _TCHAR* argv[])
{ int n,i,a,b;
f>>n;
cout<<n;
for(i=0;i<n;i++)
{
f>>a;f>>b;
cout<<a<<" ,"<<b;
g<<cmmdc(a,b);
g<<endl;
}

f.close();
g.close();
	return 0;
}

Folosesc VIsual c++ 2008 ....ce este gresit de nu imi da 0 puncte?, Asta e prima data cand trimit o solutie la vreo problema si nu prea stiu cum merg lucrurile!

[•alexandru92]

stdafx.h trebuie eliminat, aceasta biblioteca are sens doar pt IDE-ul folosit de tine si app taie iostream ( inutil ) si pune fstream in loc ( desi l-ai pus sub namespace std; ) si este main nu _tmain
ps: ai gresit fisierele ( fara .txt )
pss: problema apartie de algoritmul lui euclid, nu de algoritmul lui euclid extins

[•best4him]

mersi, pai eu am dat sa dau comentariu aici http://infoarena.ro/problema/euclid2 si vad ca l-a afisat aici , stiu ca nu trebuie <iostream> dar din obisnuinta... Thx!
Ps. De unde sa invat algoritmii de baza,? adica ce e prin manuale mi se pare putin...este vreo carte mai buna despre algoritmi?(nu vreau sa nu fie nici prea abstracta:D pentru ca nu stiu cat de mult am sa inteleg.)

[•alexandru92]

Incearca setul de 3 volume : Programare  in limbajul C/C++ pentru liceu de Emanuela Cerchez si Marinel Serban. Primul volum e pentru incepatori( clasa a 9-10 ), al doilea volum e pentru clasa 10-11, iar ultimul pentru 11-12

[•best4him]

Mersi, vad ca nu imi ia decat 40 de puncte...si e facut prin impartire...de ce?
am facut si recursiv...dar tot nu trece de 40...

Cod:

int cmmdc(int a, int b)
{  if (b==0)
	return a;
else 
return cmmdc(b,a%b);
	
}

[•dornescuvlad]

problema ar putea fi ca tu afisezi 1 daca sunt prime intre ele , in loc sa afisezi 0 cum scrie in enunt

L.E : vad ca s-a rezolvat

[•SpiderMan]

problema ar putea fi ca tu afisezi 1 daca sunt prime intre ele , in loc sa afisezi 0 cum scrie in enunt

Vezi tu undeva scris asa ceva ? NU mai posta aiurea, ca incurci oamenii .

[•cipri20]

Cod:

Cod:

include<stdio.h>
int main()
{
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  int aux,a,b,i,x;
  for(i=0;i<x;i++)
    {
      scanf("%d",&a);
      scanf("%d",&b);
    }

    while(b!=0)
     {
       aux = b;
       b = a%b;
       a = aux;


     }
  printf("%d",a);
  printf("\n");

 return 0;
}

Modificat de Moderator : Foloseste tag-ul [ code ] ... [/ code ] pentru surse!


imi spune si mie cineva de ce imi afiseaza 2?

[•alexandru92]

aux=a%b;
Nu inteleg ce are de a face cu Algoritmul lui Euclid Extins

[•SpiderMan]

Cod:

for(i=0;i<x;i++)
    {
      scanf("%d",&a);
      scanf("%d",&b);
    }

Asta ce este ? X este un numar random, pentru ca este in interiorul int-ului, si de accea b si a vor fi iarasi numere random, si probabil daca rulezi de mai multe ori o sa ai rezultat diferit.
Incearca asa:

Cod:

include<stdio.h>
int main()
{
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  int aux,a,b,i;

    scanf("%d",&a);
    scanf("%d",&b);
    
    while(b!=0)
     {
       aux = b;
       b = a%b;
       a = aux;


     }
  printf("%d",a);
  printf("\n");

 return 0;
}

EDIT: Alexandru, daca te uiti atent ALE si ALE Extins au acelasi post daca dai la comentarii, am postat la cel simplu pe forum dar nu mi-a raspuns nimeni.

[•cipri20]

Imi da la fel

[•popoiu.george]

@cipri20 M-am uitat pe sursa ta si calcularea cmmdc e corecta, doar ca tu nu tii cont ca in fisierul de intrare vor fi T teste. Si cred ca e nevoie de long long pentru 100pt.

Sper ca ti-a fost de folos.

[•SpiderMan]

@popoiu.george E suficient int , incape
@cipri20 Trebuie sa citesti prima data pe T si apoi sa faci un for in care de fiecare data calculezi cmmdc

Cod:

scanf("%d",&T);
for (i = 1; i <= T; i++)
       scanf("%d %d", &a,&b);
       ......................

[•cipri20]

 

Cod:

  #include<stdio.h>
int main()
{
 int i,a,b,r,T;
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  scanf("%d",&T);
  for(i=1;i<=T;i++)
   scanf("%d %d",&a,&b);
    do
      {
	     r=a%b;
	     a=b;
	     b=r;
      }while(r!=0);

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

imi afiseaza 1 de fiecare data  

si daca faca

Cod:

  while(b>0)
    {
      ....
    } 

la fel afiseaza
Modificat de Moderator: Nu mai posta de 2 ori consecutiv. Foloseste butonul "Modifica".

[•blasterz]

Cod:

  #include<stdio.h>
int main()
{
 int i,a,b,r,T;
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  scanf("%d",&T);
  for(i=1;i<=T;i++)
   scanf("%d %d",&a,&b);
    do
      {
	     r=a%b;
	     a=b;
	     b=r;
      }while(r!=0);

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

imi afiseaza 1 de fiecare data  

si daca faca

Cod:

  while(b>0)
    {
      ....
    } 

la fel afiseaza
Modificat de Moderator: Nu mai posta de 2 ori consecutiv. Foloseste butonul "Modifica".

Tu doar citesti in for... nu si calculezi cmmdc-ul.
Ar trebui sa faci asa (observa acoladele):

Cod:

for(i=1;i<=T;i++)
{
   scanf("%d %d",&a,&b);
    do
      {
	     r=a%b;
	     a=b;
	     b=r;
      }while(r!=0);
     printf ("%d\n", a);
}

[•cipri20]

Mersi mult mi-a iesit

[•paul_gabryel]

dece pe calculatorul meu pe exemplul lor am rezultatele
98 -147
13 -13
0 0

si cand am trimis sursa am luat 100 de puncte ?
nu inteleg imi poate explica cineva

[•SpiderMan]

In cazul in care exista mai multe solutii pentru o ecuatie, se poate afisa oricare solutie pentru care necunoscutele nu depasesc in valoare absoluta 2 000 000 000. Pentru toate ecuatiile pentru care exista solutie, va exista si o solutie cu ambele necunoscute aflate in acest interval.

Deci inseamna ca rezultatul dat de tine e bun ....
P.S. - Atat imi da si mie

[•paul_gabryel]

ioi am am sarit peste partea aceea ms )

[•AndrewTheGreat]

Poate cineva, va rog, sa imi spuna de ce cand imi declar variabilele long long nu iau 100 si cand le declar int iau 100?

Sursa 100: http://infoarena.ro/job_detail/486775
Sursa 0: http://infoarena.ro/job_detail/486766

Multumesc anticipat!

[•S7012MY]

Incearca sa folosesti %lld in loc de %I64d

[•romircea2010]

Am inteles partea cu daca c%d != 0 atunci nu exista solutii dar ma incurc la celalalt caz: de ce trebuie sa inmultim x si y cu (c/d) ca sa obtinem solutie?

[•alexandru822]

O intrebare: care e diferenta in a folosi &X sau X in functia din exemplu?