1 漢諾塔問題
2 約瑟夫環
3 求“斐波納契數列：1,1,2,3,5,8,13,21..."函數：遞歸與非遞歸
4 判斷一個數是否是 2的冪次數：
5 計算一個整數的二進制數的 1的個數num
6 輸入一個整數數組，調整數組中數字的順序，使得所有奇數位於數組的前半部分，所有偶數位於數組的後半部分。要求時間復雜度為O(n)。 ----像這種要求時間復雜度的 常常需要交換的算法
===========================================================================================
1 漢諾塔問題
//第一，把X上的n-1個盤通過Z移動到Y。
第二，把X上的最下面的盤移到Z。
//第三，因為n-1個盤全在Y上了，所以把Y當做X重復以上步驟就好了。遞歸中會保存數據
void moveNext( char pre, char next )
{
cout<<pre<<"-->"<<next<<endl;
}
void hanio(int n,char XBlock,char YBlock,char ZBlock)
{
if(n==1)
{
moveNext(XBlock,ZBlock);
}
else
{
hanio(n-1,XBlock,ZBlock,YBlock);
moveNext(XBlock,ZBlock);
hanio(n-1,YBlock,XBlock,ZBlock);
}
}2 約瑟夫環
首先建立一個 首尾相連的循環鏈表，for循環定義計算器，到達m改變鏈表的連接關系。
直到 最後剩下一個結點，pre=purnode。
typedef struct node
{
int num;
struct node *next;
}LinkNode;LinkNode * create_link( int num )
{
LinkNode *p,*current,*head; // p用來循環，current用來記錄當前的位置。head(第一個數)用來返回一個鏈表
p=(LinkNode*)malloc(sizeof(LinkNode));
p->num=1;
p->next=NULL;
head=p;
current=p;
for(int i=2;i<=num;i++)
{
//生成新的結點---建立連接----轉移到下一個
p=(LinkNode*)malloc(sizeof(LinkNode));
p->num=i;
p->next=NULL;
current->next=p;
current=p;
}
current->next=head; //鏈表的rail指向head，構成循環(循環列表list)。
return head;
}
void make_play( LinkNode *link,int mcode )
{
assert(link!=NULL&&mcode!=0);
LinkNode *pLink=link,*pPre=NULL; //錯誤：要給pre賦值才能使用。
LinkNode *pDelte; //刪除節點---free標記結點）
cout<<"親，游戲開始了！"<<endl;
while(pLink!=pPre) //最後只留一個元素。
{
for(int n=1;n<mcode;n++)
{
pPre=pLink;
pLink=pLink->next;
}
pDelte=pLink;
cout<<"出列的是"<<pDelte->num<<endl;
pPre->next=pLink->next;
pLink=pPre->next;
free(pDelte);
}
cout<<"最後出列的是："<<pLink->num<<endl;
}3 求“斐波納契數列：1,1,2,3,5,8,13,21..."函數：遞歸與非遞歸
主要就是 初始化退出條件）和循環條件轉移遞歸關系）的一個轉換的關系。
int fib( int n )
{
/*if(n==1||n==2)
{
return 1;
}
else
{
return fib(n-1)+fib(n-2);
}*/
if(n<=2)
{
return 1;
}
int valN1,valN2,sumN; //是不是可以寫成static形式的
valN1=1;
valN2=1;
//sum ,n1,n2往後移動位置
for(int i=1;i<=n-2;i++) //計算的次數
{
sumN=valN1+valN2;
valN2=valN1;
valN1=sumN;
}
return sumN;
}4 判斷一個數是否是 2的冪次數：0==(a[i]&(a[i]-1)
int find2power( int a[] ,int len)
{
int count=0;
for(int i=0;i<len;i++)
{
if(0==(a[i]&(a[i]-1)))
{
count++;
}
}
cout<<count<<endl;
return count;
}5 計算一個整數的二進制數的 1的個數num
統計一個整數的二進制數的 1的個數: num&1(一次統計最右邊的那個數值是否是1)
int num1OfBinery( int num )
{
int count=0;
while(num)
{
if(num&1)
{
count++;
}
num>>=1; //向右移動，除以2
}
return count;
}6 輸入一個整數數組，調整數組中數字的順序，使得所有奇數位於數組的前半部分，所有偶數位於數組的後半部分。要求時間復雜度為O(n)。
----像這種要求時間復雜度On）的 常常需要交換的算法：添加一個計算當前遇到的奇數個元素的mark標記標志下一個遇到的奇數應該插入的位置），遇到奇數的話---swapi，mark）
void swapElement( int arr[], int i, int mark )
{
int tmp;
tmp=arr[i];
arr[i]=arr[mark];
arr[mark]=tmp;
}
void printArrray( int arr[], int num )
{
cout<<"輸出的數組是："<<endl;
for(int i=0;i<num;i++)
{
cout<<arr[i]<<endl;
}
}
// 兩個變量：一個i遍歷數組，另一個標記需要的位置 有幾個奇數符合條件的，排在前幾位）
//1 找到第一個，判斷移動 2 循環
void partition( int arr[],int num )
{
int i=0,mark=0;
while(i<num&&(arr[i]&1==0)) //找到第一個奇數:= while +if(break)
{
i++;
}
if(i==num) //全是偶數
return;
swapElement(arr,i,mark);
i++;
mark++;
while(i<num)
{
if((arr[i]&1)==1)
{
swapElement(arr,i,mark);
mark++;
printArrray(arr,num);
}
i++;
}
printArrray(arr,num);
}===========================================================================
測試的代碼：
/*
int n;
printf("請輸入要移動的塊數：");
scanf("%d",&n);
hanio(n,'X','Y','Z');*/
int num=7;
//cout<<fib(num)<<endl;
LinkNode *head=create_link(num);
make_play(head,5);
int arr[]={1,2,3,4,5,6,7,8,16,50};
int len=sizeof(arr)/sizeof(int);
find2power(arr,len);
/*int num=7;
cout<<num1OfBinery(num)<<endl;*/
/*int arr[]={1,2,4,6,7,5,8,9};
int n=sizeof(arr)/sizeof(int);
partition(arr,n);*/
