Count-Out Puzzle NME2快速算法CODE :)

http://bbs.wenxuecity.com/math/1728230.html

http://bbs.wenxuecity.com/znjy/1728446.html

NME2=非数学小学二年级 :)

NME2 和下面的CODE得到同样结果, 但程序更初等,更直接. 因为没有实际DELETE,可以用间单ARRAY,而不用LIST.

Compile test2.cs with C-sharp to test2.exe

C:\\Windows\\Microsoft.NET\\Framework64\\v4.0.30319\\csc test2.cs

test2.cs:

using System;
using System.Collections.Generic;

class Test
{

static void Main()
{
   func(25,7);
}
// n : total number of people
// m : every m th person is removed. m

public static void func(int n, int m) {
        List people = new List\ ();
        for (int i = 1; i         {
            people.Add(i.ToString());
        }
       

        // Continue loop through the n slots again and again, until only one person is left (remove n-1 people);
        // as looping through, count the person  to m (where the slot is not null, skip null since it indicates person removed) ;
        // remove every m person by setting the his slot to null ;
 
        int remove=n-1;

        int ct = 0;
       
        while(remove>0)
        {

                for (int index = 0; index                 {
                  if(people[index] != null ) {
                   ct++;
                       if (ct==m)
                       {
                         people[index]=null ;   // flag as removed
                         ct=0;
                         remove--;
                       }
                  }

                  Console.Out.Write( " "+(people[index]==null? "X":people[index]));

              }
    
         Console.Out.WriteLine( "\\nPeople left to Remove "+remove.ToString()+ "\\n");

        }   

        // Now Only the last one person left. find him and display
        for (int index = 0; index             {
                if(people[index] != null ) {
                    Console.Out.WriteLine("Last Person: " + people[index]);
                }
            }

    }

}

 

run test2.exe output

C:> test2
 1 2 3 4 5 6 X 8 9 10 11 12 13 X 15 16 17 18 19 20 X 22 23 24 25
People left to Remove 21

 1 2 X 4 5 6 X 8 9 10 X 12 13 X 15 16 17 18 X 20 X 22 23 24 25
People left to Remove 18

 1 X X 4 5 6 X 8 9 10 X X 13 X 15 16 17 18 X 20 X X 23 24 25
People left to Remove 15

 1 X X 4 5 X X 8 9 10 X X 13 X 15 16 X 18 X 20 X X 23 24 25
People left to Remove 13

 1 X X X 5 X X 8 9 10 X X 13 X 15 X X 18 X 20 X X 23 24 25
People left to Remove 11

 1 X X X X X X 8 9 10 X X 13 X 15 X X 18 X X X X 23 24 25
People left to Remove 9

 1 X X X X X X 8 9 X X X 13 X 15 X X 18 X X X X 23 24 25
People left to Remove 8

 X X X X X X X 8 9 X X X 13 X 15 X X 18 X X X X 23 X 25
People left to Remove 6

 X X X X X X X 8 9 X X X 13 X 15 X X 18 X X X X X X 25
People left to Remove 5

 X X X X X X X 8 9 X X X 13 X 15 X X 18 X X X X X X X
People left to Remove 4

 X X X X X X X 8 9 X X X 13 X 15 X X 18 X X X X X X X
People left to Remove 4

 X X X X X X X 8 X X X X 13 X 15 X X 18 X X X X X X X
People left to Remove 3

 X X X X X X X 8 X X X X 13 X 15 X X X X X X X X X X
People left to Remove 2

 X X X X X X X 8 X X X X 13 X 15 X X X X X X X X X X
People left to Remove 2

 X X X X X X X 8 X X X X 13 X 15 X X X X X X X X X X
People left to Remove 2

 X X X X X X X X X X X X 13 X 15 X X X X X X X X X X
People left to Remove 1

 X X X X X X X X X X X X 13 X 15 X X X X X X X X X X
People left to Remove 1

 X X X X X X X X X X X X 13 X 15 X X X X X X X X X X
People left to Remove 1

 X X X X X X X X X X X X X X 15 X X X X X X X X X X
People left to Remove 0

Last Person: 15