สมมติว่าเรามีตัวเลข n เด็กสองสามคนยืนอยู่บนวงกลม มีเลขตั้งแต่ 1 ถึง n เรียงตามเข็มนาฬิกาและลูกหมายเลข 1 ถือลูกบอล อันดับแรก เด็กหมายเลข 1 โยนลูกบอลไปที่ลูกถัดไปตามเข็มนาฬิกา จากนั้นเด็กหมายเลข 2 โยนลูกบอลไปที่ลูกคนต่อไป แต่เด็กคนหนึ่ง (ให้ลูกหมายเลข 4) จากนั้นลูกคนที่สี่โยนลูกบอลให้ลูกหมายเลข 7 และ เร็วๆ นี้. เมื่อโยนลูกบอลอาจผ่านจุดเริ่มต้นของวงกลม ไม่ใช่ว่าเด็กทุกคนจะได้รับลูกบอลระหว่างการแข่งขัน ถ้าเด็กไม่ได้บอล เราต้องหาตัวเลขของเด็กที่จะได้บอลหลังการโยนแต่ละครั้ง
ดังนั้น หากอินพุตเท่ากับ n =10 เอาต์พุตจะเป็น [2, 4, 7, 1, 6, 2, 9, 7, 6]
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
p := 1 for initialize i := 1, when i < n, update (increase i by 1), do: p := p + i p := p mod n if not p is non-zero, then: p := n print p
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
void solve(int n){
int p = 1;
for (int i = 1; i < n; i++){
p += i;
p %= n;
if (!p)
p = n;
printf("%d, ", p);
}
}
int main(){
int n = 10;
solve(n);
} อินพุต
10
ผลลัพธ์
2, 4, 7, 1, 6, 2, 9, 7, 6,
