程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> Joseph Problem(詳細解法),josephproblem解法

Joseph Problem(詳細解法),josephproblem解法

編輯:關於C語言

Joseph Problem(詳細解法),josephproblem解法


前言


   這幾天學習了隊列,於是嘗試了一下Joseph Problem,然後一直有一個地方沒有通過,終於經點撥後,通過了。對於隊列的使用還是加深了印象。建議如果隊列的練手可以去嘗試解決這個問題。

 

正文


 

 

Joseph Problem(35分)   鋪墊:   假設有N個人圍成一圈,然後第一個人把第二個人殺了,刀子給第三個人,第三個人把第四個人殺了,以此類推......   首先注意:難點1:圍成一圈,我們會想用什麼數據結構呢?這麼多人,首先應該想到用數組對不對,可是怎麼表示圍成一圈呢?重點來了,其實我們可以不斷的把前面的挪到後面不就相當於圍成了圈嗎?對不對?   難點二:前一個人把後一個殺了?普通的應該會想把這個被殺的人的元素去掉,然後前一個元素往後面移,可是這樣就達不到圍成圓圈的效果了,重點來了,就是把這個殺人的人一開始也殺了,對!沒看錯,是把它也殺了,然後再把它放到放到數組的最某端就可以了。   好,難點講訴完畢。  

題目內容:

實作Joseph problem.

假設一開始有N個人,編號1~N,

按照順序以順時針圍成一個圓圈。

遊戲開始時,編號1的人拿刀。

之後每一輪刀子會被往下傳M個人,

而當輪最後拿到刀子的人會將他的下一個人殺掉,

殺完後刀子會再傳給被殺的下一個人。

這樣一輪就算結束。

遊戲會進行許多輪,直到只剩下最後一個人。

 

範例1:N=5, M=2

第一輪:刀子傳給3號,4號被殺,刀子再傳給5號 (1 2 3 5)

第二輪:刀子傳給2號,3號被殺,刀子再傳給5號 (1 2 5)

第三輪:刀子傳給2號,5號被殺,刀子再傳給1號 (1 2)

第四輪:刀子傳給1號,2號被殺,最後1號存活。

範例2:N=4, M=3

第一輪:刀子傳給4號,1號被殺,刀子再傳給2號 (2 3 4)

第二輪:刀子傳給2號,3號被殺,刀子再傳給4號 (2 4)

第三輪:刀子傳給2號,4號被殺,最後2號存活。

 

輸入格式:

輸入第一行為一個數字T,代表測資的筆數。

接下來會有T筆測資,每一筆測資一行,

會有兩個數字N,M,數字間以空格區隔。

數字範圍:

T < 1000

0 < N <= 1000

0 < M <= 1000

 

輸出格式:

輸出一行數字,將每筆測資最後存活下來的人的編號加總。

 

輸入樣例:

3

5 2

4 3

8 4

 

輸出樣例:

4

時間限制:1000ms內存限制:32000kb    

大家先嘗試解一下。再看文章比較好!

 

先理解題意:看第一個例子:刀子傳兩個人後到了第三個人,把第四個人殺了。加上又是圓圈,所以就相當與把兩個人殺了挪到後面,然後就是成了前面的問題了對不對?好,開始寫代碼。

首先我們考慮殺人這個動作。

1 int Dequeue() {
2     int z;//記錄哪個人被殺,不然要是沒有記錄,怎麼去把它挪到後面
3     z = ch[Head];
4     Head = (Head + 1) % 1000;//就是把Head指向後一人就可以了,相當於這一圓圈的人沒有它了
5     Number_of_Items--;//總人數減一
6     return z;
7 }

再考慮插到後面去這個動作:

 1 void Enqueue(int x) {
 2     if(Number_of_Items == 0) {//如果數組是空的,重新定義隊列的頭和尾
 3         Tail = Head = 0;
 4         ch[0] = x;//然後把它加進去
 5     } else {
 6         Tail = (Tail + 1) % 1000;//隊尾指向後面一個,用於存儲新的人
 7         ch[Tail] = x;
 8     }
 9     Number_of_Items++;//總人數加一10 }

接下來就是總體的設計了

        scanf("%d %d",&a,&b);//輸入總人數和要傳的人數
     for(int i=1; i <= a; i++) Enqueue(i);//把這幾人放到數組裡面去 for(int i=1; i <= a-1; i++) {//每一輪殺一個人,總共要殺n-1個人 for(int k=0; k < b%Number_of_Items; k++) { j = Dequeue(); Enqueue(j); }//每次把b個人挪到後面 j = Dequeue(); Dequeue(); Enqueue(j);//就像鋪墊所說的,殺兩個人,再把第一個人放到數組後面去。 }

注意:

1.增加數組元素時,注意要考慮當數組為空。

2.

for(int k=0; k < b%Number_of_Items; k++) {
                j = Dequeue();
                Enqueue(j);
            }

注意這段代碼,就是這個地方卡了我很久,看到沒,當b非常大的時候,運行時間要的非常久,這裡已經有3個for循環了,所以想法設法降低算法復雜度。於是發現可以對b進行優化,這是關鍵點。

3.每一次進行加入數組元素時,總人數記得加一,刪除數組元素時,總人數記得減一。

 

好,接下來寫出總代碼:

#include<stdio.h>
int ch[1000];
int Head,Tail,Number_of_Items;
 
void Enqueue(int x) {
    if(Number_of_Items == 0) {
        Tail = Head = 0;
        ch[0] = x;
    } else {
        Tail = (Tail + 1) % 1000;
        ch[Tail] = x;
    }
    Number_of_Items++;
}
 
int Dequeue() {
    int z;
    z = ch[Head];
    Head = (Head + 1) % 1000;
    Number_of_Items--;
    return z;
}
 
int main() {
    int n,j,a,b;
    int answer;
    int sum = 0;
    scanf("%d",&n);
    for(int i=0; i < n; i++) {
        scanf("%d %d",&a,&b);
        ch[1000] = 0;//注意每一次對數組的更新
        Number_of_Items=0;//對總人數的更新
        Tail = Head = 0;
        for(int i=1; i <= a; i++)
            Enqueue(i);
        for(int i=1; i <= a-1; i++) {
            for(int k=0; k < b%Number_of_Items; k++) {
                j = Dequeue();
                Enqueue(j);
            }
            j = Dequeue();
            Dequeue();
            Enqueue(j);
        }
        sum += ch[Head];
    }
    printf("%d",sum);
    return 0;
}

 

注意:每次數組用完之後,都得進行更新賦值為0,並且對總人數也得更新。

總結


  這題卡到的地方主要是如何降低算法復雜度,對其中一些變量進行優化。我也是經別人點撥才明白了這裡的優化,還得多多學習。

 

2016-03-06 14:14:02

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved