回覆列表
  • 1 # 掉眼淚的冠軍

    此題可用數學方法求解。設有n個人(編號0~(n-1)),從0開始報數,報到(m-1)的退出,剩下的人繼續從0開始報數 (用數學方法解的時候需要注意應當從0開始編號,因為取餘會取到0解。)實質是一個遞推,n個人中最終留下來的序號與n-1個人中留下來的人的序號有一個遞推關係式。假設除去第k個人,則0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1  // 原始序列 (1)0, 1, 2, 3, ..., k-2, , k, ..., n-1   // 除去第k人,即除去序號為k-1的人 (2)k, k+1, ..., n-1, 0, 1, ..., k-2  // 以序號k為起始,從k開始報0 (3)0, 1, ..., n-k-1, n-k, n-k+1, ..., n-2  // 作編號轉換,此時佇列為n-1人  (4)變換後就完完全全成為了(n-1)個人報數的子問題,注意(1)式和(4)式,是同一個問題,不同的僅僅是人數。比較(4)和(3),不難看出,0+k=k, 1+k=k+1, ... ,(3)式中"0"後面的數字,((n-3)+k)%n=k-3,((n-2)+k)%n=k-2, 對於(3)式中"0"前面的數字,由於比n小,也可看作(0+k)%n=k, (1+k)%n=k+1, 故可得出規律:設(3)中某一數為x" , (4)中對應的數為x,則有:x"=(x+k)%n.設x為最終留下的人序號時,佇列只剩下1人時,顯然x=0; 此時可向前回溯至2人時x對應的序號,3人時x對應的序號……直至n人時x的序號,即為所求。

    #include <stdio.h>const int M = 3;int main(){ int n, s = 0; scanf("%d", &n); for (int i = 2; i <= n; ++i) s = (s+M)%i; printf("%d\n", s+1); return 0;}

  • 中秋節和大豐收的關聯?
  • 大便用力,過幾天竟然有一點點便血?