題目連結:
題目大意:
給定兩正整數N、X(3 ≦ N ≦ 500,2 ≦ X ≦ N),N表示有1~N戶人家,其中第X戶為市長家。
現從第1戶家開始斷電,接下來數M戶(已斷電的不予記數,數到超過N戶,便回頭從1開始數),數到的第M戶,將其斷電。(M ≧ 2)
求其他N-1戶人家都斷電,只有市長還有電力之最小的M值為何?
解題思維:
經典的Josephus問題,只是這題只要用迴圈去跑,並模擬即可解決。
把當前的停電狀況存在一個陣列裡,並從一開始就把「1」設為「停電」的狀態(可以一個布林值陣列)。
接下來從M = 2開始,模擬出會發生的情況。當中,每遇到停電的一戶人家,就跳過不數,值到數滿M戶。
以上模擬只要剩下一戶人家或是市長家(也就是X)被斷電了,馬上跳出來。並判斷是否只剩下一戶人家,是的話,此刻的M就是我們要的答案;反之,就繼續下一個M值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。