Trebam napisati program u C++, koji izračunava najmanji zajednički sadržalac dva prirodna broja. Odakle početi? Zajednički sadržalac je najmanji broj koji se može podijeliti bez ostatka sa oba data broja. Npr., najmanji sadržilaca brojeva 2 i 3 je broj 6. UNAPRIJED HVALA!
Najmanji zajednički sadržilac dva prirodna broja
- poruka: 17
- |
- čitano: 29.996
- |
- moderatori:
Lazarus Long, XXX-Man, vincimus
- +/- sve poruke
- ravni prikaz
- starije poruke gore
1.deklariraj varijable prvi, drugi, minimalni, maksimalni i najmanjiZajednickiNazivnik
2. unesi varijable prvi i drugi
3. odredi koja je varijabla manja i pridruži je varijabli minimalni, a veću pridruži varijabli maksimalni
4 napravi ovakvu petlju:
for (int i = 1; i <= minimalni; i++)
{
if (maksimalni * i % minimalni == 0)
{
najmanjZajednickiNazivnik = i * maksimalni;
break;
}
}
Dakle na tvom primjeru za brojeve 2 i 3 petlja radi ovo:
1. iteracija
3 * 1 % 2 !=0
2. iteracija
3 * 2 % 2 == 0
Uvjet je ispunjen, varijabla najmanjiZajedničkiNazivnik dobija vrijednost 2 * 3, i petlja se prekida.
Hvala na odgovoru. Nisam baš sve pohvatao. Malo sam analizirao gore postavljenu petlju i sve sto je Floki pisao. Mislim da na ovaj način (ukoliko sam ga dobro protumačio) dobijem količnik brojeva 3 i 2 što je u ovom slučaju i najmanji zajednički činilac i što je O.K. Ali šta če biti ukoliko su u pitanju brojevi 5 i 5. Dobičemo broj 25 koji nije najmanji zajednički činilac. To bi trebao biti broj 5. Nadam se da sa svojim skromnim znanjem nisam pogrešno protumačio...?
Možda bi se ovo moglo riješiti na način da se kroz petlju dodaje unesenom broju (u ovom slučaju broju 5), broj jedan i da se dobijeni broj iz tog procesa provjeri tako što čemo taj dobijeni broj podijeliti sa 5 i to nastaviti vrtiti dok rezultat ne bude 2. Kada rezultat bude 2, onda dobijeni broj iz ove procedure uporediti sa brojem koji čemo dobiti na isti način iz druge procedure sa drugim unesenim brojem (koji je u ovom slučaju isto broj 5). Ako u ovom poređenju budu dva ista broja onda proces treba da se zaustavi i da se taj broj ispiše na ekkranu. To je onda broj 10.
Mada je u stvari rezultat trebao biti broj 5... Sada sam tek zakomplikovao i sam sebe zbunio... :)
Evo ga prva Beta Verzija. Sve radi savršeno osim kada unesem vrijednost "0" (nula)...!? Evo code pa možemo diskutovati:
/*Program koji racuna najmanji zajednicki sadrzilac dva prirodna broja
| Open Source Program NZS-001.01 BetaVersion | by Davor Damjanovic
|Kontakt:wmdcms@gmail.com www.webmarketing-design.com*/
#include<iostream>
using namespace std;
int main()
{
long int prviBroj, drugiBroj, ostatak1, ostatak2, pom_broj, brojac=0;// Deklaracija svih varijabli
cout << "Dobro dosli u program NZS-001.01 BetaVersion | by Davor Damjanovic!" << endl << "Ovo je program koji izracunava najmanji zajednicki sadrzilac dva prirodna broja." << endl
<< "Za nastavak stisnite bilo koji taster!" << endl;
system ("Pause");
cout << "Unesite prvi broj i stisnite ENTER: ";
cin >> prviBroj;// Unos prvog broja
cout << "Unesite drugi broj i stisnite ENTER: ";
cin >> drugiBroj;// Unos drugog broja
if((prviBroj==0)&&(drugiBroj==0))// Provjera unesenih brojeva, ne smiju biti nula
{cout << "Pogresan unos" << endl;
system ("Pause");
}
// Izracunavanje najmanjeg zajednickog sadrzioca
do
{
brojac=brojac+1;
ostatak1=brojac%prviBroj;
ostatak2=brojac%drugiBroj;
pom_broj=ostatak1+ostatak2;//ukljucen je pomocni broj
}
while(pom_broj!=0);//Ako je pomocni broj razlicit od nule
// Ispis rezultata
cout << "Najmanji zajednicki sadrzilac unijetih brojeva " << prviBroj << " i " << drugiBroj << " je broj " << brojac << endl;
cout << endl;
system ("Pause");
}
Hvala na odgovoru. Nisam baš sve pohvatao. Malo sam analizirao gore postavljenu petlju i sve sto je Floki pisao. Mislim da na ovaj način (ukoliko sam ga dobro protumačio) dobijem količnik brojeva 3 i 2 što je u ovom slučaju i najmanji zajednički činilac i što je O.K. Ali šta če biti ukoliko su u pitanju brojevi 5 i 5. Dobičemo broj 25 koji nije najmanji zajednički činilac. To bi trebao biti broj 5. Nadam se da sa svojim skromnim znanjem nisam pogrešno protumačio...?
Kada uneseš brojeve 5 i 5 dobiješ ovo:
1. iteracija:
5 * 1 % 5 == 0
uvjet je ispunjen
najmanjiZajednickiNazivnik = 1 * 5
Evo za 18 i 4
1. iteracija:
18 * 1 % 4 != 0
2. iteracija:
18 * 2 % 4 == 0
uvjet je ispunjen
najmanjiZajednickiNazivnik = 2 * 18
Dakle, u ovoj petlji provjerava se da li je umnožak većeg broja i brojeva u intervalu [1, manji] djeljiv sa manjim brojem, a to je matematički dovoljno za odrediti najmanji zajednički nazivnik od ta dva broja.
int gcd( int a, int b)
{
if( a%b == 0 ) return b;
return gcd( b, a%b );
}
Ako ne znaš funkcije zanemari da sam išta napisao.
int gcd( int a, int b)
{
if( a%b == 0 ) return b;
return gcd( b, a%b );
}
Ako ne znaš funkcije zanemari da sam išta napisao.
Da, ali to je najveći zajednički djeljitelj GCD, a ne najmanji zajednički nazivnik LCM
int gcd( int a, int b)
{
if( a%b == 0 ) return b;
return gcd( b, a%b );
}
Ako ne znaš funkcije zanemari da sam išta napisao.
Da, ali to je najveći zajednički djeljitelj GCD, a ne najmanji zajednički nazivnik LCM
Ispričavam se jer sam debil.
Ovo množenje večeg s koeficijentom je skroz dobro rješenje.
Ma čovjek tu lako zamjeni stvari, desi se svima nama, meni prvome.
Evo ga prva Beta Verzija. Sve radi savršeno osim kada unesem vrijednost "0" (nula)...!? Evo code pa možemo diskutovati:
/*Program koji racuna najmanji zajednicki sadrzilac dva prirodna broja
| Open Source Program NZS-001.01 BetaVersion | by Davor Damjanovic
|Kontakt:wmdcms@gmail.com www.webmarketing-design.com*/
..
(neka rješenja si već dobio, naravno ja ću o sasvim drugoj stvari jer je uočljivo).
- sam kod je trivijalan, ako već pokušavaš biti pravi profesionalac, tad počni pravilno razlikovati što znači open-free-copyright.. npr pogledaj 7z, about, licencu, copyright.
Ovo tvoje nije open source. 7z je free open software pod LGPLom. Uvjek će autor biti Pavlov, copyrightan C, dok sama izjava daje pravo korisniku, to je licenca vidi početak do Note: ..
Pa mi sad pokušaj objasniti što tvoja licenca dozvoljava, što 7z licenca. Kao i da ubaciš svoje ime umjesto autora kršio bi copyright itd.
Evo jedne dovoljno dobre definicije s Carneta, ''.. Njihova sloboda se očituje u tome da im je upotreba za bilo koju svrhu zagarantirana licencom ..'', dakle, moraš mi licencom to dozvoliti inače bi ja kao krisnik mogao biti kažnjen. Tek tad je neki software open, free, .. kad je pod takvom licencom koja garantira korisniku to pravo. Kod zatvorene-komercijalne licence tog prava (za korisnika) nema.
Tvoj kod je fizički otvoren, jer je na javno dostupnom mjestu, ali nije open softrare licenca. I dalje te zakon štiti od neovlaštenog kopiranja i svatko tko bi iskoristio tvoj kod bi bio kazneno odgovoran.
- Da bi licenca nešto dozvoljavala, mora postojati licenca, tj sadržaj-txt koji to navodi. Nije dovoljno samo napisati open, kao što nije dovoljno imati ključeve od automobila..
Za suprotni primjer, MSov zaštićen npr 1394.INF, može biti bilo koji dio koda, batch filea ili kao što je ovdje inf.
vidi header:
; 1394.INF -- This file contains descriptions of
; all supported 1394 host controllers
;
; Copyright (c) Microsoft Corporation. All rights reserved.
ili Adaptec-SAS također inf.
;
; Adaptec HostRAID SAS Adapter Driver
;
; Installation File For Microsoft Windows
;
; Version 1.0
;
; Copyright (c) Adaptec Incorporated
;
; Edited 06/22/06
;
.. -sva prava pridržana. Editiranje, distribuciju, korištenje, prodaju... To je upravo suprotno od onog što open licenca dozvoljava, to mora biti napisano. Kao što kupnjom automobila postaješ vlasnik, polaganjem vozačkog postaješ vozač, dokument je pak pisana potvrda koja to potvrđuje. Možeš znati voziti i bez dozvole tuđi automobil, ali je kažnjiivo. To je licenca (driving, software... ista stvar).
-to je prvi ozbiljan korak nakon hello world koji u profi jobu moraš svladati. Bez tog dijela možeš biti samo hibista ili code monkey.
Priložena gcd funkcija nije za odbaciti - LCM se može izračunati iz GCD:
lcm(a, b) = a * b / gcd(a, b)
Ovako ide brže nego navedeni algoritam koji testira svaku kombinaciju
@ihush Hvala na sugestiji...
/*Program koji racuna najmanji zajednicki sadrzilac dva prirodna broja
NZS-001.05BetaVersion*/
#include<iostream>
using namespace std;
int main()
{
long int prviBroj, drugiBroj, ostatak1, ostatak2, pom_broj, brojac=0;// Deklaracija svih varijabli
cout << "Dobro dosli u program NZS-001.05 BetaVersion | by Davor Damjanovic!" << endl << "Ovo je program koji izracunava najmanji zajednicki sadrzilac dva prirodna broja." << endl
<< "Za nastavak stisnite bilo koji taster!" << endl;
system ("Pause");
cout << "Unesite prvi broj i stisnite ENTER: ";
cin >> prviBroj;// Unos prvog broja
cout << "Unesite drugi broj i stisnite ENTER: ";
cin >> drugiBroj;// Unos drugog broja
while((prviBroj==0)||(drugiBroj==0))// Provjera unesenih brojeva, ne smiju biti nula
{cout << "Unijeli ste znak koji nije dozvoljen, ili nije prirodni broj!" << endl
<< "Unesite ISPRAVAN prvi broj i stisnite ENTER: " ;
cin >> prviBroj;// Ponovni unos ISPRAVNOG prvog broja
cout << "Unesite drugi broj i stisnite ENTER: ";
cin >> drugiBroj;// Ponovni unos drugog broja
};
// Izracunavanje najmanjeg zajednickog sadrzioca
do
{
brojac=brojac+1;
ostatak1=brojac%prviBroj;
ostatak2=brojac%drugiBroj;
pom_broj=ostatak1+ostatak2;//ukljucen je pomocni broj
}
while(pom_broj!=0);//Ako je pomocni broj razlicit od nule
// Ispis rezultata
cout << "Najmanji zajednicki sadrzilac unijetih brojeva " << prviBroj << " i " << drugiBroj << " je broj " << brojac << endl;
cout << endl;
system ("Pause");
}
NOVO PREPRAVLJENO: Program radi ono što sam htio. Ako korisnik upiše 0 kao ulazni podatak, program će mu ispisati sljedeču poruku "Unijeli ste znak koji nije dozvoljen, ili nije prirodni broj!" itražiti od korisnika da unese novu vrijednost: "Unesite drugi broj i stisnite ENTER"....
Priložena gcd funkcija nije za odbaciti - LCM se može izračunati iz GCD:
lcm(a, b) = a * b / gcd(a, b)
Ovako ide brže nego navedeni algoritam koji testira svaku kombinaciju
U pravu si, ovako je brže, a da se overflow odgodi što je moguće dulje, onda mala modifikacija.
LCM(a,b) = a / GCD(a, b) * b;
Najveći broj ne prelazi vrijednost LCM, što se množenjem brojeva za koje određujemo LCM događa, a to je ono što sam imao u petlji, ne množim brojeve za koje računam LCM ako ne moram.
Moram komentarisati i reči da mi ovo nije baš najjasnije.
I kako bih mogao još u program koji sam napisao uraditi sljedeče. Kada korisnik upiše neku drugu vrijednost koja nije prirodni broj treba da mu program ispiše poruku da je unio pogrešnu vrijednost. Ovo sam uradio kada korisnik upiše nulu... ali ako upiše slovo umjesto broja program zablokira.
Msilio sam to uraditi nekako ovako da u while petlju u ovaj dio koda:
while((prviBroj==0)||(drugiBroj==0))
dopišem još sljedeče
while((prviBroj==0)||(drugiBroj==0)||(prviBroj!=prirodniBrojevi)||(drugiBroj!=prirodniBrojevi))
To je ovo boldirano, što bi značilo da ukoliko prviBroj bude različit od konstante prirodniBrojevi ili drugiBroj bude različit od konstante prirodniBrojevi...
Sada bih trebao samo postaviti da konstanta ima vrijednost svih prirodnih brojeva osim 0. Je li ovo izvodljivo na ovaj način, ili nekako drugačije?
while( upisanibroj <= 0 ) upisuj ponovo;
Sad ako hočeš rješit i decimalne, moraš upisivat brojeve kao double i gledati da li je ceil( x ) == x. ( ceil je funkcija koja vraća najmanji cijeli broj koji nije manji od argumenta( odnosno x-a), sadržana je u <cmath> ako se ne varam)
ceil( 1.0000001) = 2
ceil( 1.00000000000000) = 1
dakle:
double a,b;
do
{
cin >> a >> b;
} while( (ceil(a) != a ) || ceil(b) != b || a <= 0 || b <= 0 );
Evo ovako sam nekako riješio sve:
/*Program koji racuna najmanji zajednicki sadrzilac dva prirodna broja
| NZS-001.05 BetaVersion*/
#include<iostream>
using namespace std;
int main()
{
long int prviBroj, drugiBroj, ostatak1, ostatak2, pom_broj, brojac=0;// Deklaracija svih varijabli
cout << "Dobro dosli u program NZS-001.05 BetaVersion" << endl << "Ovo je program koji izracunava najmanji zajednicki sadrzilac dva prirodna broja." << endl
<< "Za nastavak stisnite bilo koji taster!" << endl;
system ("Pause");
cout << "Unesite prvi broj i stisnite ENTER: ";
cin >> prviBroj;// Unos prvog broja
cout << "Unesite drugi broj i stisnite ENTER: ";
cin >> drugiBroj;// Unos drugog broja
// Provjera da li je broj koji se unosi prirodan broj
if(cin.fail())
{
cout << endl << "Unijeli ste znak koji nije dozvoljen, ili nije prirodni broj!" << endl
<< "Stisnite bilo koji taster da zatvorite program!" << endl;
system ("Pause");
return 0;
}
while ((prviBroj==0)||(drugiBroj==0))// Provjera unesenih brojeva, ne smiju biti nula
{
cout << "Unijeli ste znak koji nije dozvoljen, ili nije prirodni broj!" << endl
<< "Unesite ISPRAVAN prvi broj i stisnite ENTER: " ;
cin >> prviBroj;// Ponovni unos ISPRAVNOG prvog broja
cout << "Unesite drugi broj i stisnite ENTER: ";
cin >> drugiBroj;// Ponovni unos drugog broja
// Provjera da li je broj koji se unosi prirodan broj
if(cin.fail())
{
cout << endl << "Unijeli ste znak koji nije dozvoljen, ili nije prirodni broj!" << endl
<< "Stisnite bilo koji taster da zatvorite program!" << endl;
system ("Pause");
return 0;
}
};
// Izracunavanje najmanjeg zajednickog sadrzioca
do
{
brojac=brojac+1;
ostatak1=brojac%prviBroj;
ostatak2=brojac%drugiBroj;
pom_broj=ostatak1+ostatak2;//ukljucen je pomocni broj
}
while(pom_broj!=0);//Ako je pomocni broj razlicit od nule
// Ispis rezultata
cout << "Najmanji zajednicki sadrzilac unijetih brojeva " << prviBroj << " i " << drugiBroj << " je broj " << brojac << endl;
cout << endl;
system ("Pause");
}
A evo program rješen sa 3 DO-WHILE petlje. Mislim da je ovo najbolje rješenje.
/*Program koji racuna najmanji zajednicki sadrzilac dva prirodna broja
| NZS.002.00 Finalna verzija*/
/* Ukljucivanje potrebnih biblioteka koje sadrzavaju potrebne dodatne funkcije za rad ovog programa*/
#include<iostream>
using namespace std;
// Pocetak main funkcije, odnosno programa
int main()
{
// Deklaracija svih potrebnih varijabli
long int prviBroj, drugiBroj, ostatak1, ostatak2, pom_broj, brojac=0;
// Dobrodoslica i opis programa
cout << "Dobro dosli u finalnu verziju programa NZS.002.00" << endl
<< "Ovo je program koji izracunava najmanji "<< endl << "zajednicki sadrzilac dva prirodna broja." << endl
<< "Program prihvata samo prirodne brojeve N={1,2,3,...n}" << endl << endl
<< "Za nastavak stisnite ENTER!" << endl;
// Provjera PRVOG unesenog podatka
do
{
cin.clear();
cin.ignore(10, '\n');
cout << endl << "Unesite PRVI broj razlicit od nule (0): ";
cin>>prviBroj;
}while((prviBroj==0)||(cin.fail()));
// Provjera DRUGOG unesenog podatka
do
{
cin.clear();
cin.ignore(2, '\n');
cout << endl << "Unesite DRUGI broj razlicit od nule (0): ";
cin>>drugiBroj;
}while((drugiBroj==0)||(cin.fail()));
// Izracunavanje najmanjeg zajednickog sadrzioca
do
{
brojac=brojac+1;
ostatak1=brojac%prviBroj;
ostatak2=brojac%drugiBroj;
pom_broj=ostatak1+ostatak2;//ukljucen je pomocni broj
}while(pom_broj!=0);//Ako je pomocni broj razlicit od nule
// Ispis rezultata
cout << endl << "Najmanji zajednicki sadrzilac unijetih brojeva " << prviBroj << " i " << drugiBroj << " je broj " << brojac << endl;
cin.clear();
cin.ignore(1000, '\n');
//Zavrsna pozdravna poruka
cout << endl<< endl << endl << "Hvala Vam sto ste koristili program NZS.002.00 " << endl << "Stisnite bilo koji taster da zatvorite program!" << endl;
cin.clear();
cin.ignore(1000, '\n');
return 0;
};