الگوریتمهای برنامه نویسی از ساده به پیشرفته

[اشک]

الگوریتم برج هانوی:

کد:

void Hanoi(n,A,B,C)
{
if(n==1)
mov disk  #n from A to C
else
{
Hanoi(n-1,A,C,B)
mov disk  #n from A to C
Hanoi(n-1,B,A,C)
}
}

وجهه ی تاریخی الگوریتم:
در شهر هانوی،در کلیسا،کشیشان معتقد بودند که اگر فردی بتواند 128دیسک را از برج A به برج C منمتقلکند،آخرالزمان خواهد رسید.

[mscode.ir]

سلام.
یکی از دوستان راجع به اعداد بزرگ سوال کرده بود، کلا الگوریتم‌ها و کدهای زیادی براش وجود داره که اگه توی گوگل big num یا big int رو جستجو کنید خیلی از اونا رو پیدا میکنید
این کد ++C رو هم یکی از دوستانم بهم داده بود که اینجا میزارم:

کد:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <deque>
#include <string>

using namespace std ;

const long long Base = 100 * 1000 * 1000 ;
#define BASE "%08lld"

class BigNum{
   public:
   deque <long long> Num ;
   inline unsigned int size() const{ return Num.size() ; }
   BigNum(long long s=0){
      (*this) = s ;
   }
   long long operator []( const int& i ) const{
      return (i >= (int)Num.size() ? 0 : Num[i]) ;
   }
   void operator = ( const BigNum& A ){
      Num.clear() ; Num = A.Num ;
   }
   void operator = ( long long A ){
      for ( Num.clear() ; A > 0 ; A /= Base )
         Num.push_back(A % Base) ;
   }
   void operator += ( const BigNum& A ){
      long long MS = max((int)A.size(), (int)Num.size()), carry = 0 ;
      for (int i = 0 ; i < MS ; i++){
         if ( i >= (int)Num.size() ) Num.push_back(0) ;
         Num[i] = Num[i] + A[i] + carry ;
         carry = Num[i] / Base ;   Num[i] %= Base ;
      }
      while(carry){
         Num.push_back(carry) ;   carry = Num[Num.size()-1] / Base ; Num[Num.size()-1] %= Base ;
      }
   }
   void operator += ( const long long& A ){
      *this += BigNum(A) ;
   }
   void operator -= ( const BigNum& A ){
      for(int i = 0 ; i < (int)Num.size() ; i++){
         if ( Num[i] < A[i] ) Num[i] += Base, Num[i+1]-- ;
         Num[i] -= A[i] ;
      }
      while( !Num.empty() && Num[ Num.size() - 1 ] == 0 ) Num.pop_back() ;
   }
   void operator -= ( const long long& A ){
      *this -= BigNum(A) ;
   }
   void operator *= ( long long A ){
      long long carry = 0 ;
      for (int i = 0 ; i < (int)Num.size() ; i++){
         Num[i] = Num[i] * A + carry ;
         carry = Num[i] / Base ;   Num[i] %= Base ;
      }
      while(carry){
         Num.push_back(carry) ; carry = Num[Num.size()-1] / Base ; Num[Num.size()-1] %= Base ;
      }
   }
   void operator *= ( const BigNum& A ){
      BigNum O = *this ; *this = 0 ;
      for (int i = 0; i < (int)A.size() ; i++){
         BigNum tmp = O ; tmp *= A[i] ;
         for(int j = 0 ; j < i ; j++) tmp.Num.push_front(0) ;
         *this += tmp ;
      }
   }

   friend istream& operator >> ( istream& o , BigNum& A ){
      string S ; cin >> S ;
      for(int i = S.length() - 1 ; i >= 0 ; i--){
         int E = (i - 7 < 0 ? 0 : i - 7) , tmp = 0 ;
         for(int j = E ; j <= i ; j++){ tmp *= 10 ; tmp += (S[j] - '0') ; }
         A.Num.push_back(tmp) ; i = E ;
      }
      return o ;
   }
   friend ostream& operator << ( ostream& o , const BigNum& A ){
      if ( A.size() == 0 ){ printf("0\n") ;  return o ; }
      printf("%lld",A.Num[A.size()-1]) ;
      for (int i = A.size() - 2 ; i >= 0 ; i--) printf(BASE,A.Num[i]) ;
      return o ;
   }
   friend bool operator == (const BigNum& A, const BigNum& B){
      if ( A.size() != B.size() ) return false ;
      for(int i = A.size() - 1 ; i >= 0 ; i--)
         if ( A[i] != B[i] ) return false ;
      return true ;
   }
   friend bool operator < (const BigNum& A, const BigNum& B){
      if ( A.size() != B.size() ) return A.size() < B.size() ;
      for(int i = A.size() - 1 ; i >= 0 ; i--)
         if ( A[i] != B[i] ) return A[i] < B[i] ;
      return false ;
   }
};

اینم نحوه‌ی استفاده ازش

کد:

int main(){
   BigNum A(1) ; BigNum B = 1 ; BigNum C ;
   A *= 3 ; A *= B ; A -= B ;
   cin >> C ;
   C += A ; C -= A ;
   cout << C << " " << A << " " << B << endl ;
   if ( A < C || A == C )
   A *= 2 ;
}

[/quote]

[اشک]

الگوریتم bellman_ford

کد:

BELLMAN_FORD(G,w,s)
initialization_single_sorce(G,s)
for i=1 to |v[G]|-1
do for each edge(u,v)∈E[G]
do relax(u,v,w)
for each edge (u,v)∈E[G]
do if d[v]>d[u]+w(u,v)
then return FALSE
return true

تابع ریلکس یالها رو ریلکس می کنه و wوزن هر یال هست[d[u طول مسیر از روت تا رأسuهست.

[اشک]

الگوریتم ACTIVITY SELECOR

کد:

s[i,j]={a(k) ∈ s :fi<= sk< fk <= s j}

Sمجموعه فعالیتهای ارائه شده میباشد.

s={a1,a2,...,an}

ai فعالیت iام.
زمان آغاز فعالیت siو زمان پایان آن fi میباشد.

کد:

Recursive_Activity_Selector(s,f,i,n){
m=i+1
while m<=n and s(m)<f(i)
m=m+1
if(m <= n)
return( {am} U Recursive_Activity_Selector(s,f,m,n))
else
return 0;
}

برای اجرای n فعالیت باید مقدار i را هنگام فراخوانی 0 گذاشت.

[moam]

كد الگوريتم كوله پشتي بهينه

کد:

# include

# include
using namespace std;
void bi(int t[],int n){
for(int i=0; n!=0;i++){
t[i]=n%2;
n/=2;
}

}
int main()
{
int n,i,s,sum,b=-1;
cout<<"enter number of gold pocket :";
cin>>n;
cout<<"enter sum:";
cin>>s;
int temp[10]={0},a[10];
for( i=0;i<N;I++)
cin>>a[i];
for(int j=1;j<POW(2,N);J++){
bi(temp,j);
sum=0;
for(int k=0;k<N;K++){
if(temp[k]!=0)
sum+=a[k];}
if (sum==s){
for(int k=0;k<N;K++)
if (temp[k]==1)
cout<<A[K]<<" ?;
return 0;
}

[myklik]

میشه برنامه پیاده سازی الگوریتم ماتریس استراسن رو بزارید اگه میشه به زبان ویژوال

[moam]

اينهم 8وزير كه با ويژوال طراحي شده.

[moam]

اینم با تابع Decoder.
فقط یک نکته رو توجه کنید که جمله ای که میخواهید کد شود در فایل textw.txt
وجمله ای که میخواهید دیکد شود در textb.txt قرار داشته باشد.
اگر صفر و یک هایی که برای دیکد در فایل textb.txt میریزید نمادی از هیچ حرفی (با توجه به کد شدن در مرحله ی قبل) نباشند برنامه تک بوق میزند و دیکد کردن می ایستد.
همانطوری که قبلا گفتم این دو فایل در دایرکتوری خود برنامه ایجاد شوند.
اینم کد کامل:

کد:

//Written by Soheil setayeshi
//www.codecorona.com
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
//*******************************Datatype : Node
class node
{
      public:
             int num;
             char ch;
             node *right;
             node *left;
             node():num(0),ch(0),right(0),left(0){}
};
//*******************************Datatype : Code
class code
{
      public:
             char bcode[8];
             char ch;
             code(){for(int i=0;i<8;i++) bcode[i]=0;}
};
//*******************************Class : Huffman
class huffman
{
      public:
             huffman();  
      private:
              void reader();
              void lister();
              void sort();
              void create();
              void binary(node*,char[],int);
              void coder();
              void calculate();
              void display();
              void decoder();
              vector<char> sentence;//Sentence
              vector<char> codes;//Coded letters
              vector<node> list;//Letters with num
              vector<node*> v;//Address of letters in list
              code *dictionary;//Binary map
              string btext;//Input binary
                
};
//*******************************Constractor
huffman :: huffman()
{
        int i;
        reader();
        lister();
        sort();
        dictionary=new code[list.size()];
        for (i=0;i<list.size();i++)
            dictionary[i].ch=v[i]->ch;
        calculate();
}
//*******************************Reader
void huffman :: reader ()
{
     char ch;
     ifstream in("textw.txt",ios::in);
     while (in.get(ch))
           sentence.push_back(ch);
     in.close();
}
//*******************************Lister
void huffman :: lister ()
{
     int i,j;
     node temp;
     temp.ch=sentence[0];
     temp.num=1;
     list.push_back(temp);
     for (i=1;i<sentence.size();i++)
     {
         for (j=0;j<list.size();j++)
             if (sentence[i]==list[j].ch)
             {
                list[j].num++;
                break;
             }
         if (j==list.size())
         {
            temp.ch=sentence[i];
            list.push_back(temp);
         }
     }
     for (i=0;i<list.size();i++)
         v.push_back(&list[i]);
}
//*******************************Sorter
void huffman :: sort()
{
     for (int i=0;i<v.size()-1;i++)
         for (int j=0;j<v.size()-i-1;j++)
             if( v[j]->num > v[j+1]->num )
                 swap( v[j] , v[j+1]);
}
//*******************************Calculate
void huffman :: calculate()
{
     char s[8]={0};
     create();
     binary(v[0],s,0);
     coder();
     display();
}
//*******************************Create
void huffman :: create()
{
     if (v.size() > 1 )
     {
        node *p1=v[0],*p2=v[1],*p=new node;
        p->right=p2;
        p->left=p1;
        p->num=p1->num + p2->num;
        v.erase(v.begin());
        v.erase(v.begin());
        v.insert(v.begin(),p);
        sort();
        create();
     }
     else return;
}
//*******************************Binary
void huffman :: binary(node* n,char byte[],int i)//n: First address  
{                                                //byte[]: Binary code place
                                                 //i: Present place of pointer    

     if ( ! n->ch )
     {
        char byte1[8]={0},byte2[8]={0};//1:right  2:left
        strcpy(byte1,byte);
        strcpy(byte2,byte);
        byte1[i]='1';
        byte2[i]='0';
        binary(n->right,byte1,i+1);
        binary(n->left,byte2,i+1);
     }
     else
     {
         for (int j=0;j<list.size();j++)
             if (dictionary[j].ch == n->ch)
             {
                strcpy(dictionary[j].bcode,byte);
                return;
             }
     }    
}
//*******************************Display
void huffman :: display()
{
     int i;
     cout<<"Input sentence is: ";
     for (i=0;i<sentence.size();i++)
         cout<<sentence[i];
     cout<<"\n\n";
     for (i=0;i<list.size();i++)
         cout<<list[i].ch<<':'<<list[i].num<<' ';
     cout<<"\n\n";
     for (i=0;i<list.size();i++)
         cout<<dictionary[i].ch<<" -> "<<dictionary[i].bcode<<endl;
     cout<<endl;
     cout<<"\nThe Huffman code of input words is(from textw.txt):\n";
     for (i=0;i<codes.size();i++)
         cout<<codes[i];
     cout<<"\n\n";
     decoder();
     cout<<endl;
    
}
//*******************************Coder
void huffman :: coder()
{
     for (int i=0;i<sentence.size();i++)
         for (int j=0;j<list.size();j++)
             if (dictionary[j].ch == sentence[i])
             {
                for (int k=0 ; dictionary[j].bcode[k] ; k++)
                    codes.push_back(dictionary[j].bcode[k]);
                break;
             }
}
//*******************************Decoder
void huffman :: decoder()
{
     ifstream in("textb.txt",ios::in);
     in>>btext;
     cout<<"Input binaries is(from textb.txt):\n";
     cout<<btext<<endl;
     cout<<"\nThe Huffman decode of input binaries is: ";
     int l,i,j,k,length;
     for (l=0;l<btext.size();)
     {
         for (i=list.size()-1 ; i>=0 ;i--)
         {
             length=strlen(dictionary[i].bcode);
             char *temp=new char[length];
             for (k=l,j=0;k<l+length;k++,j++)
                 temp[j]=btext[k];
             if (strstr(temp,dictionary[i].bcode))
             {
                cout<<dictionary[i].ch;
                l+=length;
                break;
             }
             if (i == 0)//end of dictionanry
             {
                cout<<"\n\aOut of dictionaty!!\n";
                system("pause");
                return;
             }
         }
     }
     cout<<endl;
}
//*******************************Main
int main()
{
    huffman ob;
    system("pause");
    return 0;
}
//*******************************End

[moam]

جمله n ام فیبوناچی (بازگشتی)شبه كد

کد:

int fib  (int n)
  {
       if ( n <= 1)
            return n;
       else
            return fib (n – 1)  + fib (n – 2);
  }

[moam]

اینم کد برنامه n وزیر که قبلا 8 وزیرش رو گذاشته بودم البته این با c++ هستش

[moam]

الگوریتم جمله nام فیبوناچی (تکراری)

کد:

int fib2 (int n)
   {
       index i;
       int f [0..n];
       f[0] = 0;
       if (n > 0)  {
              f[1] = 1;
              for  (i = 2 ; I <= n; i++)
                  f[i] = f [i -1] + f [i -2];
      }
      return  f[n];
  }

---

الگوریتم سری ان فیبوناچی (تکراری)

کد:

int fib2 (int n)
   {
       index i;
       int f [0..n];
       f[0] = 0;
       if (n > 0)  {
              f[1] = 1;
              for  (i = 2 ; I <= n; i++)
                  f[i] = f [i -1] + f [i -2];
      }
      return  f[n];
  }