出圈問題的鍊錶解法

2022-12-09 11:09:01 字數 1200 閱讀 8152

出圈問題的鍊錶解法(經典之作)

出圈問題是上級考試中最難的題之一,可以說如果能獨立解決這個問題那麼其他的題自然不在話下。

傳統的解法使用了一種橋難理解的複雜演算法,在這裡我提供一種相對來說更易理解的演算法「環鏈表模擬法」

題目57:設有n個人圍坐一圈並按順時針方向從1到n編號,從第s個人開始進行1到m的報數,報數到第個m人,此人出圈,再從他的下乙個人重新開始1到m的報數,如此進行下去直到所有的人都出圈為止。現要求按出圈次序,每10人一組,給出這n個人的順序表。

請考生編制函式josegh()實現此功能並呼叫函式writedat()把結果p輸出到檔案中。

設n=100,s=1,m=10.

(1)將1到n個人的序號存入一維陣列p中;

(2)若第i個人報數後出圈,則將p[i]置於陣列的倒數第i個位置上,而原來第i+1個至倒數第i個元素依次向前移動乙個位置;

(3)重複第(2)步直至圈中只剩下p[1]為止。

部分源程式已給出。

請勿改動主函式main()和輸出資料函式writedat()的內容。

下面是原題答案:

void josegh(void) /*標準答案*/

}注:題中第乙個for()迴圈是先對陣列p賦初值。在第二個for()中用i來控制沒出圈的

總人數,s1=(s1+m-1)%i的作用是找出報數後出圈人的下標,其中對i求餘的作用是使報

數按圈進行(即報到尾後又從頭報),該演算法在很多題目中都用到。由於求餘的作用當

報數正好到最後乙個時s1為0,故而要進行if(s1==0)的判斷。內嵌的for()迴圈是將出圈

以後的人依次往前移。

環鏈表模擬法

void josegh(void)

m; /*定義結構體*/

typedef m *link;

m *h,*s,*r; /*定義指標*/

int i,j,a[100]=;

h=malloc(sizeof(m));

h->n=1;

r=h;

for(i=2;i<=100;i++) /*賦初值*/

r->next=h;

r=r->next;

for(i=0;i<100;i++)

a[i]=r->next->n;

h=r->next;

r=r->next=h->next;

free(h);

printf("%d\t",a[i]);}}

應用問題的算術解法與代數解法

從小學到中學,數學課程最顯著的變化,就是從算術學習到代數和幾何的學習 僅就代數來說,它的基本課題是著眼於利用運算來討論各種數學問題 從發展的角度看,代數學是在 數 與 運算 的基礎上有系統地發展起來的 首先擴大了數的範圍,從正整數 正分數和零發展到有理數 實數 其次,在用字母表示數的基礎上,應用 運...

應用問題的算術解法與代數解法

例1 某農場計畫播種小麥與大豆共138公頃,種小麥的面積是種大豆面積的4倍 試問該農場應種小麥與大豆各多少公頃?算術解法由本題所給的條件可知,播種總面積等於種大豆面積的 4 1 倍,因此種大豆的公頃數 總播種公頃數 4 1 種小麥的公頃數 總播種公頃數 種大豆的公頃數,即 138 4 1 27.6 ...

關於追及問題的解法

教學目的 1 借助 線段圖 分析複雜問題中的數量關係。2 能用一元一次方程解決實際生活中的相遇 追及問題。3 培養學生的分析 解決問題能力。教學重點 運用方程解決實際問題。教學難點 能畫出 線段圖 分析行程中的等量關係。教學過程 一 匯入 同學們!你家離學校大約幾公尺?平時上學你需要幾分鐘?點名學生...