約瑟夫環-(數組、循環鏈表、數學)

約瑟夫環(約瑟夫問題)是一個數學的應用問題:已知n個人(以編號1,2,3...n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數,數到m的那個人出列;他的下一個人又從1開始報數,數到m的那個人又出列;依此規律重復下去,直到圓桌周圍的人全部出列。

?

約瑟夫環運作如下:

1、一群人圍在一起坐成環狀(如:N)

2、從某個編號開始報數(如:S)

3、數到某個數(如:M)的時候,此人出列,下一個人重新報數

4、一直循環,直到所有人出列??,約瑟夫環結束

模擬過程,求出最后的人。

把數組看成一個環,從第s個元素開始按m-1間隔刪除元素,重復過程,直到元素全部去掉。

?

void Josephus(int a[],int n,int m,int s)
{int i,j;int k=n;for(i=0;i<n;i++)a[i]=i+1;//編號i=(s+n-1)%n;while(k){for(j=1;j<m;j++)i=(i+1)%k;//依次報數,頭尾相連printf("%d\n",a[i]);//出局for(j=i+1;j<k;j++)a[j-1]=a[j];//刪除本節點k--;}//模擬結束,最后輸出的就是留下的人
}

?

可以用帶頭單循環鏈表來求解:

也是一樣的,只是實現不同,給出核心代碼:

    while(k){for(j=1;j<m;j++){pr=p;p=p->link;if(p==head)//頭結點跳過{pr=p;p=p->link;}}k--;//打印pr->link=p->link;//刪結點free(p);p=pr->link;//從下一個繼續}

雙向循環鏈表也可以解,和單鏈表類似,只是不需要保持前趨指針。

?

數學可解:

效率最高


int check_last_del(int n,int m)
{int i = 1;int ret = 0;for (i = 2; i<=n;i++)ret = (ret + m) %i;return ret+1;//因為ret是從0到n-1,最后別忘了加1。
}

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/445580.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/445580.shtml
英文地址,請注明出處:http://en.pswp.cn/news/445580.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Ubuntu麒麟下搭建FTP服務

一.怎么搭建FTP服務&#xff1a; 第一步>>更新庫 linuxidclinuxidc:~$ sudo apt-get update 第二步>>采用如下命令安裝VSFTPD的包 linuxidclinuxidc:~$ sudo apt-get install vsftpd 第三步>>安裝完成后打開 /etc/vsftpd.conf 文件&#xff0c;按如下所述…

《數據結構上機實驗(C語言實現)》筆記(1 / 12):緒論

文章目錄驗證性實驗求1~n的連續整數和說明放碼結果常見算法時間函數的增長趨勢分析說明放碼結果設計性實驗求素數個數說明放碼結果求連續整數階乘的和說明放碼結果驗證性實驗 求1~n的連續整數和 說明 對于給定的正整數n&#xff0c;求12…n12…n12…n&#xff0c;采用逐個累…

線性表實現一元多項式操作

數組存放&#xff1a; 不需要記錄冪&#xff0c;下標就是。 比如1&#xff0c;2&#xff0c;3&#xff0c;5表示12x3x^25x^3 有了思路&#xff0c;我們很容易定義結構 typedef struct node{float * coef;//系數數組int maxSize;//最大容量int order;//最高階數 }Polynomial…

ubuntu下解壓縮zip,tar,tar.gz和tar.bz2文件

在Linux下面如何去壓縮文件或者目錄呢&#xff1f; 在這里我們將學習zip, tar, tar.gz和tar.bz2等壓縮格式的基本用法。 首先了解下Linux里面常用的壓縮格式。 在我們探究這些用法之前&#xff0c;我想先跟大家分享一下使用不同壓縮格式的經驗。當然&#xff0c;我這里講到的只…

《數據結構上機實驗(C語言實現)》筆記(2 / 12):線性表

文章目錄驗證性實驗實現順序表各種基本運算的算法放碼sqlist.hsqlist.cppexp2-1.cpp結果實現單鏈表各種基本運算的算法放碼linklist.hlinklist.cppexp2-2.cpp結果實現雙鏈表各種基本運算的算法放碼dlinklist.hdlinklist.cppexp2-3.cpp結果實現循環單鏈表各種基本運算的算法放碼…

鏈表排序-歸并

鏈表排序&#xff0c;可以插入排序&#xff0c;我就不寫了。 實現歸并排序 歸并排序&#xff08;MERGE-SORT&#xff09;是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法&#xff08;Divide and Conquer&#xff09;的一個非常典型的應用。將已有序的子序列合并&…

ubuntu麒麟下安裝并啟用搜狗輸入法

1.首先打開UK軟件&#xff0c;輸入搜狗尋找搜狗拼音軟件 然后下載搜狗拼音軟件 接著點擊啟動該軟件 2.點擊搜狗拼音的圖標&#xff0c;進入搜狗拼音的設置窗口 點擊高級&#xff0c;并打開FCITX設置 加入英語輸入法 3.這樣就可以進行中英文切換了

線性表表示集合

集合我們高中都學過吧&#xff1f; 最重要的幾個特點&#xff1a;元素不能重復、各個元素之間沒有關系、沒有順序 集合內的元素可以是單元素或者是集合。 對集合的操作&#xff1a;交集并集差集等&#xff0c;還有對自身的加減等。 需要頻繁的加減元素&#xff0c;所以順序…

家用無線路由器購買入門指南

視頻一&#xff1a;「白問」普通大眾 買路由器關注這幾個點就夠了 來源 例如商品名&#xff1a;AC 1200M 雙頻 AX前綴wifi6IEEE 802.11 AX AC前綴wifi5IEEE 802.11 AC AX比AC好 1200M 理論峰值 和網速無關 商家噱頭 MIMO SU-MIMO 單用戶多進多出&#xff08;早期&#xff…

ubuntu linux下執行.sh文件

ubuntu linux下執行.sh文件 首先&#xff0c;要確保這個文件的類型是可執行的。 有兩種辦法把文件設置為可執行文件。 1) 直接在文件屬性標簽中選中 "可執行"&#xff0c;--b 如果用的是圖形界面&#xff0c;這個方法最簡單直接。 2) 使用命令 chmod x file.sh。將可…

鏈表相交問題

本來想自己寫&#xff0c;寫了一半發現一篇文章&#xff0c;解釋寫得簡單易懂&#xff0c;我就直接拿過來了。 這個問題值得反復地寫&#xff0c;鍛煉鏈表coding能力的好題。 //如果兩個鏈表都不帶環 int NotCycleCheckCross(pLinkNode head1,pLinkNode head2) {pLinkNode lis…

用JS寫了一個模擬串行加法器

在重溫《編碼&#xff1a;隱匿在計算機軟硬件背后的語言》第12章——二進制加法器時&#xff0c;心血來潮用JS寫了一個模擬串行加法器。 測試斷言工具TestUtils.js function assertTrue(actual){if(!actual)throw "Error actual: " actual " is not true.&q…

Android學習路線總結

title: Android學習路線總結&#xff0c;絕對干貨 tags: Android學習路線,Android學習資料,怎么學習android grammar_cjkRuby: true --- 一、前言 不知不覺自己已經做了幾年開發了&#xff0c;由記得剛出來工作的時候感覺自己能牛X&#xff0c;現在回想起來感覺好無知。懂的越…

雙棧

利用棧底位置相對不變的特性&#xff0c;可以讓兩個順序棧共享一個空間。 具體實現方法大概有兩種&#xff1a; 一種是奇偶棧&#xff0c;就是所有下標為奇數的是一個棧&#xff0c;偶數是另一個棧。但是這樣一個棧的最大存儲就確定了&#xff0c;并沒有起到互補空缺的作用&a…

Error when loading the SDK:解決方案

錯誤情況&#xff1a; 當打開eclipse時出現如下窗口&#xff08;內容如下&#xff09; Error when loading the SDK: Error: Error parsing \Android\adt-bundle-windows-x86_64-20140702\sdk\system-images\android-22\android-wear\armeabi-v7a\devices.xml cvc-complex-type…

單調隊列優化的背包問題

對于背包問題&#xff0c;經典的背包九講已經講的很明白了&#xff0c;本來就不打算寫這方面問題了。 但是吧。 我發現&#xff0c;那個最出名的九講竟然沒寫隊列優化的背包。。。。 那我必須寫一下咯嘿嘿&#xff0c;這么好的思想。 我們回顧一下背包問題吧。 01背包問題 …

用Python去除掃描型PDF中的水印

內容概述 含水印掃描型PDF文件&#xff0c;其中某頁如下圖所示&#xff0c;用Python去除其頁頂及頁底的水印。 處理思路&#xff1a;PDF中的每一頁的水印的相對位置基本相同&#xff0c;將PDF每一頁輸出成圖片&#xff0c;然后進行圖片編輯&#xff0c;用白色填充方形覆蓋水印…

鏈表實現棧

棧&#xff0c;是操作受限的線性表&#xff0c;只能在一端進行插入刪除。 其實就是帶尾指針的鏈表&#xff0c;尾插 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define Status int #define SElemType int //只在頭部進行插入和刪除(…

二階有源濾波器

濾波器是一種使用信號通過而同時抑制無用頻率信號的電子裝置, 在信息處理、數據傳送和抑制干擾等自動控制、通信及其它電子系統中應用廣泛。濾波一般可分為有源濾波和無源濾波, 有源濾波可以使幅頻特性比較陡峭, 而無源濾波設計簡單易行, 但幅頻特性不如濾波器, 而且體積較大。…

用JS寫了一個30分鐘倒計時器

效果圖 額外功能 左鍵單擊計時器數字區&#xff0c;不顯示或顯示秒鐘區。左鍵雙擊計時器數字區&#xff0c;暫停或啟動計時器。計時完畢&#xff0c;只能刷新頁面啟動計時器。輸入框可輸入備注信息&#xff0c;輸入框失去焦點或計時完畢后&#xff0c;時間戳附帶備注信息會存入…