面试题:最后一人开始时的位置?

题目

50人排一队,从1开始报数,3倍数的退出,到尾后头的人接着报(如第2轮时第1个人报51),问最后1人开始时的位置?

代码

C#代码1(int[]版,退出的保留其位置):
using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //条件
            int number = 50;
            int interval = 3;
            int[] ids = new int[number];
            for (int i = 0; i < number; i++) ids[i] = 1;

            //辅助变量
            int balance = number;
            int j = 0;

            //报数,3倍数退出
            while (balance != 1)
            {
                for (int k = 0; k < number; k++)
                {
                    if (ids[k] == 0)
                        continue;

                    if (++j % interval == 0)
                    {
                        ids[k] = 0;
                        balance--;

                        if (balance == 1) break;
                    }
                }
            }

            //原来位置查询
            for (int i = 0; i < number; i++)
            {
                if (ids[i] == 1)
                {
                    Console.WriteLine("最后1人开始时的位置为:{0}", i + 1); //11
                    break;
                }
            }

            Console.Read();

        }
    }
}

C#代码2(List<int>版,退出的不保留位置,后边的前移):
using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //条件
            int number = 50;
            int interval = 3;
            List<int> ids = new List<int>();
            for (int i = 0; i < number; i++) ids.Add(i + 1);


            //辅助变量
            int balance = ids.Count;
            int j = balance;

            //报数,3倍数退出
            while (balance != 1)
            {
                for (int k = balance - 1; k >= 0; k--)
                {
                    if ((j - (balance - k - 1)) % interval == 0)
                        ids.RemoveAt(k);
                }

                balance = ids.Count;
                j += balance;
            }

            //原来位置查询
            Console.WriteLine("最后1人开始时的位置为:{0}", ids[0]); //11

            Console.Read();

        }
    }
}


上一篇: Web.config好用,但不宜滥用
下一篇: .NET内存分配浅析
文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags:
最新日志:
评论: 0 | 引用: 0 | 查看次数: 3317
发表评论
登录后再发表评论!