欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++經(jīng)典算法之約瑟夫問(wèn)題詳解

 更新時(shí)間:2021年07月31日 09:59:49   作者:是一只派大鑫  
這篇文章主要給大家介紹了關(guān)于C/C++經(jīng)典算法之約瑟夫問(wèn)題的相關(guān)資料,約瑟夫環(huán)問(wèn)題是一道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)的題目,本文介紹了解決約瑟夫問(wèn)題的三種方法,需要的朋友可以參考下

什么是約瑟夫問(wèn)題? 

約瑟夫問(wèn)題:n個(gè)人圍成一圈,初始編號(hào)從1~n排列,從約定編號(hào)為x的人開始報(bào)數(shù),數(shù)到第m個(gè)人出圈,接著又從1開始報(bào)數(shù),報(bào)到第m個(gè)數(shù)的人又退出圈,以此類推,最后圈內(nèi)只剩下一個(gè)人,這個(gè)人就是贏家,求出贏家的編號(hào)。

是不是有點(diǎn)點(diǎn)復(fù)雜,其實(shí)該問(wèn)題歸結(jié)為模擬類型的算法題,根據(jù)題目要求模擬即可。

我說(shuō),一行代碼解決約瑟夫問(wèn)題!

???我去

別著急,我們一步一步學(xué)習(xí)

方法一:數(shù)組

在第一次遇到這個(gè)題的時(shí)候,我是用數(shù)組做的,我猜絕大多數(shù)人也都知道怎么做。方法是這樣的:

用一個(gè)數(shù)組來(lái)存放 1,2,3 ... n 這 n 個(gè)編號(hào),如圖(這里我們假設(shè)n = 6, m = 3)

 然后不停著遍歷數(shù)組,對(duì)于被選中的編號(hào),我們就做一個(gè)標(biāo)記,例如編號(hào) arr[2] = 3 被選中了,那么我們可以做一個(gè)標(biāo)記,例如讓 arr[2] = -1,來(lái)表示 arr[2] 存放的編號(hào)已經(jīng)出局的了。

然后就按照這種方法,不停著遍歷數(shù)組,不停著做標(biāo)記,直到數(shù)組中只有一個(gè)元素是非 -1 的,這樣,剩下的那個(gè)元素就是我們要找的元素了。我演示一下吧:

 

這種方法簡(jiǎn)單嗎?思路簡(jiǎn)單,但是編碼卻沒那么簡(jiǎn)單,臨界條件特別多,每次遍歷到數(shù)組最后一個(gè)元素的時(shí)候,還得重新設(shè)置下標(biāo)為 0,并且遍歷的時(shí)候還得判斷該元素時(shí)候是否是 -1。用這種數(shù)組的方式做,千萬(wàn)不要覺得很簡(jiǎn)單,編碼這個(gè)過(guò)程還是挺考驗(yàn)人的。

這種做法的時(shí)間復(fù)雜度是 O(n * m), 空間復(fù)雜度是 O(n);

下面給出數(shù)組方法的參考代碼:

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
	int a[1001]={0}; //初始化化數(shù)組作為環(huán)
	int n,m;//n代表總的人數(shù),m代表報(bào)數(shù)到幾退出
	cin>>n>>m;
	int count=0;//記錄退出的個(gè)數(shù)
	int k=-1;//這里假定開始為第一個(gè)人,下標(biāo)為0,編號(hào)為1,如需從編號(hào)x開始,則k=x-2
	while(count<n-1){  //總共需要退出n-1個(gè)人
		int i=0;//記錄當(dāng)前報(bào)數(shù)編號(hào)
		while(i<m){
			k=(k+1)%n; //循環(huán)處理下標(biāo)
			if(a[k]==0){
				i++;
				if(i==m){
					a[k]=-1;
					count++;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==0){
			printf("%d\n",i+1);
			break;
		}
	}
	return 0;
}

方法二:環(huán)形鏈表

學(xué)過(guò)鏈表的人,估計(jì)都會(huì)用鏈表來(lái)處理約瑟夫環(huán)問(wèn)題,用鏈表來(lái)處理其實(shí)和上面處理的思路差不多,只是用鏈表來(lái)處理的時(shí)候,對(duì)于被選中的編號(hào),不再是做標(biāo)記,而是直接移除,因?yàn)閺逆湵硪瞥粋€(gè)元素的時(shí)間復(fù)雜度很低,為 O(1)。當(dāng)然,上面數(shù)組的方法你也可以采用移除的方式,不過(guò)數(shù)組移除的時(shí)間復(fù)雜度為 O(n)。所以采用鏈表的解決方法如下:

1、先創(chuàng)建一個(gè)環(huán)形鏈表來(lái)存放元素:

2、然后一邊遍歷鏈表一遍刪除,直到鏈表只剩下一個(gè)節(jié)點(diǎn),我這里就不全部演示了

 

感興趣的友友可以自己實(shí)現(xiàn)以下代碼,這里就不放了

下面我們來(lái)看看,是如何一行代碼實(shí)現(xiàn)約瑟夫問(wèn)題!

方法三:遞歸

其實(shí)這道題還可以用遞歸來(lái)解決,遞歸是思路是每次我們刪除了某一個(gè)人之后,我們就對(duì)這些人重新編號(hào),然后我們的難點(diǎn)就是找出刪除前和刪除后編號(hào)的映射關(guān)系。

我們定義遞歸函數(shù) f(n,m) 的返回結(jié)果是存活士兵的編號(hào),顯然當(dāng) n = 1 時(shí),f(n, m) = 1。假如我們能夠找出 f(n,m) 和 f(n-1,m) 之間的關(guān)系的話,我們就可以用遞歸的方式來(lái)解決了。我們假設(shè)人員數(shù)為 n, 報(bào)數(shù)到 m 的人就自殺。則剛開始的編號(hào)為

… 1 ... m - 2

m - 1

m

m + 1

m + 2 ... n …

進(jìn)行了一次刪除之后,刪除了編號(hào)為 m 的節(jié)點(diǎn)。刪除之后,就只剩下 n - 1 個(gè)節(jié)點(diǎn)了,刪除前和刪除之后的編號(hào)轉(zhuǎn)換關(guān)系為:

刪除前 --- 刪除后

… --- …

m - 2 --- n - 2

m - 1 --- n - 1

m ---- 無(wú)(因?yàn)榫幪?hào)被刪除了)

m + 1 --- 1(因?yàn)橄麓尉蛷倪@里報(bào)數(shù)了)

m + 2 ---- 2

… ---- …

新的環(huán)中只有 n - 1 個(gè)節(jié)點(diǎn)。且刪除前編號(hào)為 m + 1, m + 2, m + 3 的節(jié)點(diǎn)成了刪除后編號(hào)為 1, 2, 3 的節(jié)點(diǎn)。

假設(shè) old 為刪除之前的節(jié)點(diǎn)編號(hào), new 為刪除了一個(gè)節(jié)點(diǎn)之后的編號(hào),則 old 與 new 之間的關(guān)系為 old = (new + m - 1) % n + 1。

 注:有些人可能會(huì)疑惑為什么不是 old = (new + m ) % n 呢?主要是因?yàn)榫幪?hào)是從 1 開始的,而不是從 0 開始的。如果 new + m == n的話,會(huì)導(dǎo)致最后的計(jì)算結(jié)果為 old = 0。所以 old = (new + m - 1) % n + 1. 這樣,我們就得出 f(n, m) 與 f(n - 1, m)之間的關(guān)系了,而 f(1, m) = 1.所以我們可以采用遞歸的方式來(lái)做。

 代碼如下:

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

臥槽,以后有人讓你手寫約瑟夫問(wèn)題,你就扔這一行代碼給它。 

總結(jié)

到此這篇關(guān)于C/C++經(jīng)典算法之約瑟夫問(wèn)題的文章就介紹到這了,更多相關(guān)C/C++約瑟夫問(wèn)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語(yǔ)言容易被忽視的函數(shù)設(shè)計(jì)原則基礎(chǔ)

    C語(yǔ)言容易被忽視的函數(shù)設(shè)計(jì)原則基礎(chǔ)

    C語(yǔ)言的設(shè)計(jì)目標(biāo)是提供一種能以簡(jiǎn)易的方式編譯、處理低級(jí)存儲(chǔ)器、產(chǎn)生少量的機(jī)器碼以及不需要任何運(yùn)行環(huán)境支持便能運(yùn)行的編程語(yǔ)言.那么C語(yǔ)言函數(shù)設(shè)計(jì)的一般原則和技巧都是怎樣的呢,下面帶你了解
    2022-04-04
  • 淺談C++ Socket編程

    淺談C++ Socket編程

    本文給大家簡(jiǎn)單介紹了C++中的Socket編程的種類以及sockets編程的8個(gè)步奏,簡(jiǎn)單生動(dòng),有需要的小伙伴可以參考下
    2017-07-07
  • C語(yǔ)言代碼實(shí)現(xiàn)簡(jiǎn)單掃雷小游戲

    C語(yǔ)言代碼實(shí)現(xiàn)簡(jiǎn)單掃雷小游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-01-01
  • opencv檢測(cè)直線方法之投影法

    opencv檢測(cè)直線方法之投影法

    這篇文章主要為大家詳細(xì)介紹了opencv檢測(cè)直線之投影法的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-12-12
  • C++ stringstream格式化輸出輸入詳情

    C++ stringstream格式化輸出輸入詳情

    這篇文章主要介紹了C++ stringstream格式化輸出輸入,首先string str; cin>>str;遇到空格結(jié)束;于是乎產(chǎn)生了getline(),可與得到一行字符串;空格自動(dòng)去掉,下面來(lái)看看文章的詳細(xì)內(nèi)容,需要的小伙伴可以參考一下
    2021-11-11
  • 一篇文章帶你實(shí)現(xiàn)C語(yǔ)言中常用庫(kù)函數(shù)的模擬

    一篇文章帶你實(shí)現(xiàn)C語(yǔ)言中常用庫(kù)函數(shù)的模擬

    這篇文章主要介紹了C語(yǔ)言中常用庫(kù)函數(shù)的模擬,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09
  • 詳細(xì)解析命令行的getopt_long()函數(shù)

    詳細(xì)解析命令行的getopt_long()函數(shù)

    getopt_long支持長(zhǎng)選項(xiàng)的命令行解析,函數(shù)中的參數(shù)argc和argv通常直接從main()的兩個(gè)參數(shù)傳遞而來(lái)
    2013-09-09
  • C++ Boost PropertyTree解析INI文件詳解

    C++ Boost PropertyTree解析INI文件詳解

    Boost PropertyTree庫(kù)不僅可以解析JSON,XML格式,還可以直接解析INI格式文件。這篇文章就是為大家介紹一下如何通過(guò)Boost PropertyTree解析INI文件,需要的可以參考一下
    2022-01-01
  • c++命名對(duì)象和匿名對(duì)象的解析

    c++命名對(duì)象和匿名對(duì)象的解析

    像按值傳遞的對(duì)象(函數(shù)入?yún)?,函?shù)返回值)都是匿名對(duì)象,那匿名對(duì)象的特點(diǎn)是什么呢?下面通過(guò)實(shí)例代碼給大家解析c++命名對(duì)象和匿名對(duì)象的相關(guān)知識(shí),感興趣的朋友一起看看吧
    2021-10-10
  • C++內(nèi)存對(duì)象布局小測(cè)試

    C++內(nèi)存對(duì)象布局小測(cè)試

    這篇文章主要介紹了C++內(nèi)存對(duì)象布局小測(cè)試,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-12-12

最新評(píng)論