当前位置:网站首页>7-8 7104 Joseph problem (PTA program design)
7-8 7104 Joseph problem (PTA program design)
2022-07-06 13:56:00 【Programming Lindaiyu】
Joseph's question : Yes n Only monkey , Circle clockwise to choose the king ( Number from 1 To n), From 1 We'll start counting on the , Count to m, Count to m The monkey out of the circle , The rest of the monkeys went on from 1 Start counting . That's it , Until there's only one monkey left in the circle , This monkey is the monkey king , Programming for input n,m after , Output the number of the last Monkey King .
Input format :
Each line is two integers separated by spaces , The first is n, The second is m ( 0 < m, n < 300) . The last line is :0 0 .
Output format :
For each row of input data ( Except for the last line ), The output data is also a line , The number of the last Monkey King .
sample input :
6 2
12 4
8 3
0 0
sample output :
5
1
7
Code (Python):
Method 1 :
n,m=map(int,input().split()) # Input n,m
list1=[] # For storage “ monkey ”
list2=[] # Used to store the final results
f=0 # There are several groups
for i in range(300): # First, add elements to the list , Otherwise, the list is empty , Cannot modify elements in the list
list1.append(0)
while 1:
if n==0 and m==0: # Input “0 0” when , end
break
else: # Or start choosing the monkey king
for i in range(1,n+1): # Because the monkey sequence is from 1 At the beginning , So our list also starts from 1 Start
list1[i]=1 # First initialize the numbers in the list so that they are all 1, use 1 To show the monkeys that have not been eliminated
f+=1 # Count , A total of several groups of numbers were calculated , Last act list2 The length of , use for Output results
i=1 # Start with the first number
sum=n # At the beginning n individual 1
count=0 #count Namely 1~m
while sum>1: #sum by n In number 1 The number of , Remnant 1 individual 1 It means that the monkey king has been selected
if list1[i]!=0: # Not for everyone 0 Number of numbers ( Monkeys that have not been eliminated ),count+1
count+=1
if count==m: # until count Add to equal m When , Count to m The monkey out of the circle
count=0 #count Start counting again
list1[i]=0 # Make the corresponding element equal to 0, It means that it has been eliminated
sum-=1 #sum Number of minus 1, It means that there are few monkeys 1
i+=1 # Every time a monkey is eliminated ,i Add 1, Start looking for the next monkey
if i==n+1: # After subscript exceeds the range , Just go back to the beginning and find , It is equivalent to forming a circle
i=1
for i in range(1,n+1): # Traverse the list
if list1[i]!=0: # Look for not 0 The position of the number of , That is, the serial number of the monkey king
list2.append(i) # And add its serial number to the result list
n,m=map(int,input().split()) # Input again , Ready for the next cycle
for i in range(f): # Output the results in the result list
print(list2[i])
Method 2 :
n,m=map(int,input().split()) ## Input n,m
wang=[] # For storage “ monkey ”
while 1:
if n==0 and m==0 : # Input “0 0” when , end
break
else: # Or start choosing the monkey king
k=0 #k Indicates the order of reported amount , Set it to 0
wang.clear() # First empty the last monkey sequence
for i in range(1,n+1): # take n Monkey from 1 Numbered starting
wang.append(i)
while len(wang) > 1: #wang The length of the list is greater than 1 when , It means that the monkey king has not been elected , Into the loop
i=0
while i<len(wang): # Traverse all monkeys in the king list
k+=1 # From 1 We'll start counting on the , Count to m, Every time I report k Add 1
if k == m: # When k Add to m when , It means that the monkey just counts to m
del wang[i] # Eliminate the monkey , Delete it from the list
k=0 # The rest of the monkeys went on from 1 Start counting , So first of all k Set as 0
# Be careful , On the count of m when , Delete the monkey , So the number of monkeys behind it will be reduced by one , therefore i No need to add 1 You can directly judge the next monkey
else: # If k It's not equal to m, Then the monkey will not be eliminated , send i Add 1, Start judging the next monkey
i+=1
a=wang[0] # Last , Out of the while loop , There must be only one monkey left , The monkey king
print(a) # Because it existed at the beginning wang In the list is the serial number of each monkey , So the value in the direct output is the serial number of the monkey
n,m=map(int,input().split()) # Input again , Ready for the next cycle
Ideas : The above provides two ways to solve this problem , It's basically the same , Are stored through a list “ monkey ”, Then gradually eliminate the selected monkeys , Finally find the monkey king . The difference lies in , In method 1 , First save the data in the list “1” To show the monkeys that have not been eliminated , Then count to m The monkey is set 0 Indicates elimination , There is only one left in the final list “1” when , It means to choose the monkey king . In method two , The serial number of the monkey is directly stored in the list , Then count to m The monkey of is directly deleted from the list , The only remaining element in the final list is the monkey king .
The above program gives more detailed comments , For novice Xiaobai's reference . The idea of program design or code implementation is not optimal , You are welcome to correct your mistakes or give better ideas .
I am a rookie who wants to be Kunpeng , Everyone's encouragement is my driving force , Welcome to like collection comments !
边栏推荐
- .Xmind文件如何上传金山文档共享在线编辑?
- 深度强化文献阅读系列(一):Courier routing and assignment for food delivery service using reinforcement learning
- String ABC = new string ("ABC"), how many objects are created
- MATLAB打开.m文件乱码解决办法
- JS several ways to judge whether an object is an array
- 简单理解ES6的Promise
- [three paradigms of database] you can understand it at a glance
- 简述xhr -xhr的基本使用
- 【MySQL数据库的学习】
- FAQs and answers to the imitation Niuke technology blog project (III)
猜你喜欢
[au cours de l'entrevue] - Comment expliquer le mécanisme de transmission fiable de TCP
4. Branch statements and loop statements
The difference between cookies and sessions
PriorityQueue (large root heap / small root heap /topk problem)
QT meta object qmetaobject indexofslot and other functions to obtain class methods attention
(original) make an electronic clock with LCD1602 display to display the current time on the LCD. The display format is "hour: minute: Second: second". There are four function keys K1 ~ K4, and the fun
About the parental delegation mechanism and the process of class loading
C language Getting Started Guide
[VMware abnormal problems] problem analysis & Solutions
. Net6: develop modern 3D industrial software based on WPF (2)
随机推荐
Mixlab unbounded community white paper officially released
Strengthen basic learning records
Custom RPC project - frequently asked questions and explanations (Registration Center)
7-9 制作门牌号3.0(PTA程序设计)
实验七 常用类的使用(修正帖)
简单理解ES6的Promise
Simply understand the promise of ES6
UGUI—Text
1143_ SiCp learning notes_ Tree recursion
Force deduction 152 question multiplier maximum subarray
Analysis of penetration test learning and actual combat stage
【数据库 三大范式】一看就懂
Leetcode.3 无重复字符的最长子串——超过100%的解法
[modern Chinese history] Chapter V test
仿牛客技术博客项目常见问题及解答(三)
Zatan 0516
The difference between abstract classes and interfaces
2. First knowledge of C language (2)
强化学习基础记录
About the parental delegation mechanism and the process of class loading