7-8 7104 Joseph problem (PTA program design)

Joseph's question ： Yes ｎ Only monkey , Circle clockwise to choose the king （ Number from １ To ｎ）, From １ We'll start counting on the , Count to ｍ, Count to ｍ 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 ｎ,ｍ 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 １ We'll start counting on the , Count to ｍ, 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 ！