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

深入理解約瑟夫環(huán)的數(shù)學優(yōu)化方法

 更新時間:2013年05月24日 09:36:51   作者:  
本篇文章是對約瑟夫環(huán)的數(shù)學優(yōu)化方法進行了詳細的分析介紹,需要的朋友參考下
首先,約瑟夫環(huán)的數(shù)學優(yōu)化方法為:
為了討論方便,先把問題稍微改變一下,并不影響原意:問題描述:n個人(編號0~(n-1)),從0開始報數(shù),報到(m-1)的退出,剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。
我們知道第一個人(編號一定是(m-1)%n) 出列之后,剩下的n-1個人組成了一個新的約瑟夫環(huán)(以編號為k=m%n的人開始):      k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2   并且從k開始報0?,F(xiàn)在我們把他們的編號做一下轉換:
k --> 0   k+1 --> 1   k+2 --> 2
n-1 --> n-1-k     0--> n-k  
        ... ...   
k-3 --> n-3   k-2 --> n-2
序列1: 1, 2, 3, 4, …, n-2, n-1, n
序列2: 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n
序列3: k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1   
序列4:1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1   
變換后就完完全全成為了(n-1)個人報數(shù)的子問題,假如我們知道這個子問題的解:例如x是最終的勝利者,那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎??。∽兓厝サ墓胶芎唵?,相信大家都可以推出來:
∵ k=m%n;   
∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n
∴x'= (x+ m%n)%n = (x+m)%n   得到 x‘=(x+m)%n
如何知道(n-1)個人報數(shù)的問題的解?對,只要知道(n-2)個人的解就行了。(n-2)個人的解呢?當然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題!好了,思路出來了,下面寫遞推公式:
令f表示i個人玩游戲報m退出最后勝利者的編號,最后的結果自然是f[n].
遞推公式:   f[1]=0;   f[i]=(f[i-1]+m)%i; (i>1)
完整的實現(xiàn)代碼如下:
復制代碼 代碼如下:

/*
約瑟夫環(huán)遞推公式:令f[i]表示i個人玩游戲報m退出最后勝利者的編號,最后的結果自然是f[n] 
遞推公式  f[1]=0;  f[i]=(f[i-1]+m)%i; (i>1)
*/
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
 int n, m,i, f[20]={0};
 scanf("%d %d",&n,&m);
    for(i=2;i<=n;i++)
 {
  f[i]=(f[i-1]+m)%i;
  printf("%d個人報數(shù),報到%d的出列,最后的勝者下標為%d\n", i,m,f[i]);
 }
    printf("The winner is %d\n", f[n]+1);
 system("pause");
}

優(yōu)化后的代碼為:
復制代碼 代碼如下:

#include "stdio.h"
#include "stdlib.h"
int main(void)
{
    int n, m,i, s=0;
 scanf("%d %d",&n,&m);
    for(i=2;i<=n;i++)
 {
  s=(s+m)%i;
 }
    printf("The winner is %d\n", s+1);
 system("pause");
}

相關文章

  • C 語言快速排序實例代碼

    C 語言快速排序實例代碼

    本文主要介紹了C語言的快速排序算法,這里給大家舉例說明并附代碼實例,需要的朋友可以參考下
    2016-07-07
  • VS Code 中安裝運行、編寫C語言程序的詳細教程

    VS Code 中安裝運行、編寫C語言程序的詳細教程

    這篇文章主要介紹了VS Code 中安裝運行、編寫C語言程序的詳細教程,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-03-03
  • 基于QT制作一個簡易的傳輸文件小工具

    基于QT制作一個簡易的傳輸文件小工具

    本文主要介紹了通過QT實現(xiàn)的一個文件傳輸小工具。功能就是能實現(xiàn)文件的雙向傳輸,即客戶端能傳給服務端,服務端可以傳給客戶端。文中示例代碼具有一定的學習價值,感興趣的小伙伴可以了解一下
    2021-12-12
  • 一文帶你分清C++的定義,聲明和初始化

    一文帶你分清C++的定義,聲明和初始化

    這篇文章主要為大家詳細介紹了C++的定義,聲明,初始化,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C語言判斷大小端的兩種方法

    C語言判斷大小端的兩種方法

    大小端的問題在很多面試筆試中都會遇到,本文主要介紹了C語言判斷大小端的兩種方法,文中通過示例代碼介紹的非常詳細,需要的朋友們下面隨著小編來一起學習學習吧
    2024-02-02
  • C++返回值類型后置實現(xiàn)(跟蹤返回值類型)

    C++返回值類型后置實現(xiàn)(跟蹤返回值類型)

    本文主要介紹了C++返回值類型后置實現(xiàn),文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • C++學習小結之二進制轉換

    C++學習小結之二進制轉換

    這篇文章主要介紹了C++學習小結之二進制轉換的相關資料,需要的朋友可以參考下
    2015-07-07
  • 使用map實現(xiàn)單詞轉換的實例分析

    使用map實現(xiàn)單詞轉換的實例分析

    本篇文章是對使用map實現(xiàn)單詞轉換的代碼實例進行了纖細的分析介紹,需要的朋友參考下
    2013-05-05
  • C語言中socket相關網(wǎng)絡編程函數(shù)小結

    C語言中socket相關網(wǎng)絡編程函數(shù)小結

    這篇文章主要介紹了C語言中socket相關網(wǎng)絡編程函數(shù)小結,是C語言入門學習中的基礎知識,需要的朋友可以參考下
    2015-09-09
  • C++ vector 遍歷的幾種方法

    C++ vector 遍歷的幾種方法

    本文主要介紹了C++ vector 遍歷的幾種方法,對vector 遍歷有一定的總結,具有一定的參考價值,感興趣的可以了解一下
    2021-07-07

最新評論