題目一
快速找到未知長度的單鏈表的中間節(jié)點(diǎn)
普通方法
由于單鏈表不知道長度扒吁，必須遍歷完整個單鏈表才知道單戀表的長度律姨，然后根據(jù)一般的長度去找中間結(jié)點(diǎn)，這是普通方法。
問的是快速找到砰琢，當(dāng)然要用快速的方法啦
有一個很巧妙的方法蘸嘶，快慢指針
快指針每次走2個結(jié)點(diǎn)，慢指針每次走1個結(jié)點(diǎn)陪汽，當(dāng)快指針走完鏈表训唱，慢指針剛好走到中間，這就是快慢指針的核心思想挚冤。
int GetMidNode(node* L) //尋找鏈表中間值
{
int a;
node *search,*mid;
mid = search = L;
while(search->next != NULL)
{
if(search->next->next != NULL)
{
search = search->next->next;
mid= mid->next;
}
else
{
search = search->next;
}
}
a = mid->data;
return a;
}
題目二
約瑟夫環(huán)
問題描述：N個人圍成一圈况增，從第一個人開始報(bào)數(shù)，報(bào)到m的人出圈训挡，剩下的人繼續(xù)從1開始報(bào)數(shù)澳骤，報(bào)到m的人出圈；如此往復(fù)澜薄，直到所有人出圈为肮。（模擬此過程，輸出出圈的人的序號）
循環(huán)單鏈表解法：
#include<stdio.h>
#include <stdlib.h>
typedef struct node//節(jié)點(diǎn)存放一個數(shù)據(jù)和指向下一個節(jié)點(diǎn)的指針
{
int data;
struct node* pnext;
} Node;
Node *link_create(int n)//創(chuàng)建n個節(jié)點(diǎn)的循環(huán)鏈表
{
//先創(chuàng)建第1個節(jié)點(diǎn)
Node *p,*q,*head;
int i ;
p = (Node *)malloc(sizeof(Node));
head = p;
p->data = 1;
for(i = 2;i<=n;i++)//再創(chuàng)建剩余節(jié)點(diǎn)
{
q = (Node *)malloc(sizeof(Node));
q->data = i;
p->pnext = q;
p = q;
}
p->pnext = head;//最后一個節(jié)點(diǎn)指向頭部肤京，形成循環(huán)鏈表
return head;
}
void link_process(Node *head,int k,int m)//從編號為k(1<=k<=n)的人開始報(bào)數(shù)颊艳，數(shù)到m的那個人出列；
{
int i;
Node *p = head,*tmp1;
while(p->data != k)//p指向的節(jié)點(diǎn)data為k
{
tmp1 = p;
p = p->pnext;
}
while(p->pnext != p)
{
for(i=1;i<m;i++)
{
tmp1 = p;
p = p->pnext;
}
printf("%d ",p->data);
tmp1->pnext= p->pnext;
free(p);
p = tmp1->pnext;
}
printf("%d ",p->data);
free(p);
}
int main()
{
Node *head = link_create(5);
link_process(head,3,1);
system("pause");
return 0;
}
C++數(shù)列推導(dǎo)實(shí)現(xiàn)（數(shù)學(xué)推導(dǎo)式）
推導(dǎo)求解
現(xiàn)在考慮一種泛化情形：總共有 n 個人忘分，數(shù)到 k 的人被殺掉棋枕，其中 n >= k。幸存者的位置為 pn 妒峦。
顯而易見重斑，初始位置為 k 的人將會第一個被殺掉。此時(shí)肯骇，經(jīng)過重新排序之后绸狐，問題變成了 n-1 個人的情形。幸存者的位置為 pn-1 累盗。如果能夠找到從 pn-1 到 pn 的遞推關(guān)系寒矿，那么問題就解決了。
重新排序之后若债，每個人的位置發(fā)生了下面這些變化：
- 1 -> n-k+1
- 2 -> n-k+2
- ...
- k-1 -> n-1
- k 被殺死
- k+1 -> 1
- ...
- pn -> pn-1
- ...
- n-1 -> n-k+1
- n -> n-k
很容易我們能得到這樣一個關(guān)系式：pn = (pn-1 + k) % n 符相。再加上剛才討論的特例，只有一個人的情況時(shí)，p1 = 1 啊终。遞推式就已經(jīng)很明顯了镜豹。
當(dāng)然上文只討論了 n>=k 的情形，實(shí)際上對于 n<k 的情形蓝牲，剛才所得到的遞推式依然適用趟脂，我們就不展開討論了。
#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::cin;
using std::list;
int main()
{
int total = 0;
cout << "Please input total number of people : ";
cin >> total;
int number = 0;
cout << "Please input selected number : ";
cin >> number;
/* If number = 3
* f(1) = 0
* f(2) = 1 = (f(1) + 3) % 2
* f(3) = 1 = (f(2) + 3) % 3
* f(4) = 0 = (f(3) + 3) % 4
* f(5) = 3 = (f(4) + 3) % 5
* ...
* f(n) = x = (f(n-1) + 3) % n
* */
int last = 0; // f(1) = 0
for(int i = 2; i <= total; ++i)
{
last = (last + number) % i;
}
cout << "The last one is : " << last + 1 << endl;
return 0;
}
