Silnia
Największy wspólny dzielnik
Sortowanie
Ciąg Fibonacciego
Szukanie liczb pierwszych
Literatura
|
silnia metodą rekurencyjną
#include "stdafx.h"
#include <iostream.h>
unsigned long int silnia (unsigned n)
{
if(n==0) return 1;
else return n*silnia(n-1);
};
unsigned n;
int main(int argc, char* argv[])
{
cout<<"podaj liczbę "<<endl;
cin>>n;
cout<<silnia(n)<<endl;
return 0;
}
Największy wspólny dzielnik, algorytm Euklidesa
#include <cstdlib>
#include <iostream>
using namespace std;
int nwd(int a,int b)
{
int p=0;
while(a!=b)
{
if(a>b)
{
p=a;
a=b;
b=p;
}
a=a-b;
}
return a;
}
int main(int argc, char *argv[])
{
int la,lb;
cout<<"Podaj pierwszą liczbę"<<endl;
cin>>la;
cout<<"Podaj druga liczbę"<<endl;
cin>>lb;
cout<<"Największy wspólny dzielnik "<<la<<" i "<<lb<<" jest rowny "<<nwd(la,lb)<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
Sortowanie
Sortowanie przez wstawianie
#include <cstdlib>
#include <iostream>
using namespace std;
int n;
int * sort(int p[],int n)
{
int key = 0;
int i=0;
for(int j=1;j<n;j++)
{
key=p[j];
i=j-1;
while ((i>=0)&&(p[i]>key))
{
p[i+1]=p[i];
i--;
}
p[i+1]=key;
}
return p;
}
void druk(int p[],int n)
{
cout<<"posortowana tablica:"<<endl;
for(int i=0;i<n;i++) cout<<p[i]<<endl;
}
int main(int argc, char *argv[])
{
cout<<"Podaj wymiar tablicy do sortowania"<<endl;
cin>>n;
int * p;
p=new int[n-1];
for(int i=0;i<n;i++){cin>>p[i];}
p=sort(p,n);
druk(p,n);
system("PAUSE");
return EXIT_SUCCESS;
}
Metodą bąbelkową
#include "stdafx.h"
#include <iostream.h>
int main(int argc, char* argv[])
{
int n=0;
int t=0;
int * p;
cout<<"podaj ilosć elementów"<<endl;
cin>n;
p=new int [n];
cout<<"wpisz kolejne wartości"<<endl;
for(int i=0;i<n;i++)cin>>p[i];
for(int l=0;l<n;l++)
{
for(int j=1;j<(n-l);j++)
{
if (p[j-1]>p[j])
{
t=p[j-1];
p[j-1]=p[j];
p[j]=t;
};
}
}
cout<<"Posortowana tablica"<<endl;
for(int k=0;k<n;k++) cout<<p[k]<<endl;
delete [] p;
cin>>n;
return 0;
}
Ciąg Fibonacciego
#include "stdafx.h"
#include <iostream.h>
#include <time.h>
unsigned fib(unsigned n)
{
if((n==0)||(n==1)) return 1;
else return fib(n-2)+fib(n-1);
};
unsigned n;
int main(int argc, char* argv[])
{
time_t start, stop;
cout<<"podaj liczbę "<<endl;
cin>>n;
start=time(NULL);
for(unsigned i=0;i<=n;i++) cout<<fib(i)<<endl;
stop=time(NULL);
cout<<"czas wykonania "<<(stop-start)<<endl;
return 0;
}
Aby obliczyć tą metodą kolejną n-tą wartość ciągu, musi być wykonane w przybliżeniu
20.69n wywołań funkcji fib. W metodzie zaprezentowanej poniżej
wystarczy n operacji dodawania i przypisania.
#include "stdafx.h"
#include <iostream.h>
#include <time.h>
unsigned n;
int main(int argc, char* argv[])
{
time_t start, stop;
cout<<"podaj liczbę"<<endl;
cin>>n;
start=time(NULL);
unsigned * p;
p=new unsigned[n+1];
p[0]=1;
p[1]=1;
for(unsigned i=2;i<=n;i++)
{
p[i]=p[i-1]+p[i-2];
}
for(unsigned j=0;j<=n;j++) cout<<p[j]<<endl;
stop=time(NULL);
cout<<"czas wykonania "<<(stop-start)<<endl;
delete [] p;
return 0;
}
Najprostrza metoda obliczenia kolejnych 'a' wyrazów ciągu Fibonacciego
#include <iostream>
using namespace std;
int a;
unsigned long int fib(int a)
{
unsigned long int p=1,n=1, s=0;
for(int i=1;i<=a;i++)
{
if((i==1)||(i==2)) s=1;
else
{
s=p+n;
p=n;
n=s;
}
cout<<"wyraz "<<i<<" to: "<<s<<endl;
}
return s;
}
int main()
{
cout<<"ile wyrazów ciągu Fibonaciego wyliczyć?"<<endl;
cin>>a;
fib(a);
}
Szukanie liczb pierwszych
Metoda brutalna polegająca na sprawdzeniu kolejnych liczb, dzieląc ją
przez wszystkie licby mniejsze lub równe pierwiastkowi z liczby będącej kandydatką
na liczbę pierwszą.
#include "stdafx.h"
#include <io.h>
#include <iostream.h>
#include <fstream.h>
int main(int argc, char* argv[])
{
unsigned long int max, candid = 2, div = 2;
int chck=1;
cout<<"podaj liczbę"<<endl;
cin>>max;
ofstream plik;
plik.open("prime.txt");
while (candid<= max)
{
div=2;
chck=1;
while((div*div<=candid)&& (chck!=0))
{
if(candid%div == 0)chck = 0;
div++;
}
if(chck)
{
cout<<candid<<endl;
plik<<candid<<endl;
}
candid++;
}
plik.close();
return 0;
}
Liczenie można przyśpieszyć ograniczając się do sprawdzenia warunku
czy kandydatka do liczby pierwszej dzieli się bez reszty przez liczby
pierwsze takie, że ich kwadrat jest mniejszy lub równy w stosunku do
kandydatki.
#include "stdafx.h"
#include <io.h>
#include <iostream.h>
#include <fstream.h>
typedef unsigned long bign;
struct nprim
{
bign bn;
nprim * next;
};
int freenprim(nprim * head)
{
int i=1;
nprim *curr=head;
while(i)
{
nprim *nextp=curr->next;
delete curr;
if(nextp==NULL) i=0;
else curr=nextp;
}
return 0;
};
void find(bign max)
{
ofstream plik;
plik.open("prime.txt");
nprim * first;
first=new nprim;
nprim *last=first;
first->bn=2;
first->next=NULL;
bign cand=2;
while(cand<=max)
{
nprim * curr=first;
int check=1;
while(curr->bn*curr->bn<=cand)
{
if(cand%curr->bn==0)
{
check=0;
break;
};
curr=curr->next;
}
if(check)
{
cout<<cand<<endl;
plik<<cand<<endl;
last->next=new nprim;
last=last->next;
last->bn=cand;
last->next=NULL;
}
cand++;
}
freenprim(first);
plik.close();
}
int main(int argc, char* argv[])
{
bign max;
cout<<"podaj liczbe"<<endl;
cin>>max;
find(max);
cin>>max;
return 0;
}
|