Liczby szczęśliwe
Kod był wyświetlany 2417 razy.
    /*
Name: Liczby szczesliwe
Copyright: GPL GNU
Date:10-05-09 13:01
Description: 
Dla danej liczby N (dla N < 100000), należy wyświetlić ostatnią 
liczbę szczęśliwą mniejszą od N.     

 Algorytm ustalania liczb szczęśliwych:
          
 Mamy szereg liczb: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,...
        A = {a1, ..., an} = {1, 2, 3, ..., n}
        
Iteracja 1: usuwamy co drugą liczbę z początkowego ciągu liczb. 
Usuwamy elementy począwszy od drugiego elementu ciągu. 
        A := A - {a2, a4, a6, ...}

Iteracja 2: Z pozostałych elementów ciągu pobieramy drugi element (jest nim 3). 
A zatem usuwamy w 2 iteracji co 3 element ciągu. 

Iteracja n: Bierzemy n-ty element ciągu, który powstał po (n-1) iteracji. 
Jest nim an. W związku z tym usuwamy co an-ty element ciągu. Przykładowo 
w 4 iteracji element a4 = 7, a zatem z ciągu usuwamy co siódmy element.    
*/
#include <iostream>

using namespace std;
int main()
{
int i,j,k=3,newk=0,l=2,m,n;
bool *tab;
do
{
  cout<<"\n\n\tPodaj N: ";
  cin>>n;
  }
while(n<2);

n--;
tab=new bool[n];
for(i=0;i<n;i++)           //wykonanie pierwszej iteracji
{
                if((i+1)%2==0)
                tab[i]=false;
                else
                tab[i]=true;
                }

do
{
  m=0;
  j=0;
  for(i=0;i<n;i++)
  {
                  if(tab[i]==true)     //jezeli liczby jeszcze nie sa wyrzucone
                  {
                                  j++;        
                                  if(j==k)    //kiedy dojdzie do k-tego elementu
                                  {
                                          tab[i]=false;  //wyrzuc go
                                          j=0;           //i licz od nowa
                                          }
                                  else
                                  {
                                      m++;  //ile jeszcze zostalo niewyrzuconych 
                                      if(newk==0&&m>l) //wyznacz nowe k
                                      newk=i+1;
                                      }              
                                  }
                  }
k=newk;
newk=0;
l++;  //iteracja
}
while(k<=m);    //dopuki ilosc elementow ciagu jest wystarczajaca do wyrzucania
 
for(i=n-1;i>=0;i--)
{
                   if(tab[i]==true)
                   {
                                   cout<<"\n\t"<<i+1<<"\n\n\t";
                                   break;
                                   }
                   }
delete(tab);
system("pause");
return 0;
}
    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT