食人族吃人问题

今天下午进行了2012年的学校软件设计比赛.得了个三等奖.

我和两个个同学组队,一共有十道题目.

一等奖做了5道题目.

二等奖两组,分别都是做了四个题目.

三等奖都是做了三个题目.

-----------------------------------背景介绍完毕分割---------------------------------

其中一道题目是这样的:

有一群人来到了一个荒岛,然后被食人族抓到了,食人族要吃了他们,但是可以有一个人能活下来.

食人族吃人的顺序是从第一个人开始吃,然后隔一个人,再吃下一个如果是5个人那么吃人的顺序就是1 3 5 4

排在第二的人就有生还机会.

并且还给了两个输入输出的数值供判断:

输入:5

输出:2

输入:10

输出:4

---------------------------------------------------题目割--------------------

可能我是第一次参加这种比赛,平时写程序也没有在这种环境中,所以状态并不是很好,做出来的三道题目都是同学做的,

我去打了个酱油.

于是心情很糟糕,回来后就一直在想这个问题并开始动手写程序.经过几番改写也终于写出来了.

注释蛮多的.应该是我能想到的比较简单的方法.如果你有好的办法.请留言指点谢谢~

本人水平:c#初学者不对之处望教导.

/*
 * 食人族吃人问题,求最后一个生还者应该开始坐在第几个位置.
 * User: Administrator
 * iAte: 2012/12/5
 * Time: 17:31
 */
using System;

namespace shirenzu
{
    class Program
    {
        public static void Main(string[] args)
        {
            //定义部分
            //i为循环变量 同时也是吃人的增加变量
            //iTem是当有人被吃掉后往前移动的临时存放变量
            //a是一共有多少人
            int i,iTem;
            int a;
            
            //输入部分输入有多少人存入到a并开辟指定大小的空间用于存放人数
            Console.WriteLine("请输入人数:");
            a = Convert.ToInt32(Console.ReadLine());
            int[] iA=new int[a];
            
            
            //给每个人编号虽然数组从0开始但是编号从1开始
            for (i=0;i<iA.Length ;i++ ) {
                iA[i]=i+1;
            }
            
            i = 0;
            //处理部分------------------------------------
            while (a > 1) {
                iA[i] = 0;
                
                //每吃掉一个人就把所有人往前移动
                for (int j =i; j < iA.Length-1; j++)
                {
                    iTem = iA[j];
                    iA[j] = iA[j + 1];
                    iA[j + 1] = iTem;
                }
                //因为所有人都向前移动了一位所以下一个被吃的人就是i+1
                i = i + 1;
                //吃掉一个则少了一个人
                a--;
                
                //i=a则等于当前人数了后面的都是死人  所以让i=0从新开始
                if (i == a) {
                    i = 0;
                }
                //i如果大于a说明要绕回来了 因为大家是坐成一个圈的 所以i要从i-a开始
                if (i > a) {
                    i = i - a;
                }

                
            }
            
            //输出部分------------------------------
            for (i=0;i<iA.Length ;i++ ) {
                if (iA[i] != 0) {
                    Console.Write(iA[i]);
                }
                
                
            }
            Console.ReadKey();
        }
    }
}

老师给了我一种方法,比我的这种执行效率高了几百倍,其实不用把活着的人往前移动,只需要隔一个人吃一个人就行了.

代码如下:

using System;

class Program
{
    static void Main(string[] args)
    {
        int i;
        int a;
        int iCount;
        bool flg;
        string s;

        while (true)
        {
            //输入部分输入有多少人存入到a并开辟指定大小的空间用于存放人数
            s = Console.ReadLine();
            if (string.IsNullOrEmpty(s)) break;
            a = Convert.ToInt32(s);
            int[] iA = new int[a];
            
            
            //给全部的人都赋值1代表这个人活着---------------
            for (i = 0; i < iA.Length; i++)
            {
                iA[i] = 1;
            }
            
            
            //初始化开始条件--------------------------------
            i = 0;
            iCount = 0;
            flg = true;
            
            
            //吃掉的人比开始的人少1个的时候，循环结束----------------
            while (iCount < a - 1)
            {
                //当前位置有人
                if (iA[i] > 0)
                {
                    //被吃的情况
                    if (flg)
                    {
                        iA[i] = 0;
                        iCount++;
                        //吃完一个，下个不吃
                        flg = false;
                    }
                    else
                    {
                        flg = true;
                    }
                }
                i++;
                //最后一个位置，再回到开头
                if (i == a)
                {
                    i = 0;
               }
            }
            
            
            //输出部分------------------------------
            for (i = 0; i < iA.Length; i++)
            {
                if (iA[i] != 0)
                {
                   Console.WriteLine(i + 1);
                }
            }
        }
    }
}

顺便说一下.这个比赛的好处就是告诉了我,

我有多么的差劲而不是厉害,很多东西以为做出来就行了,

其实有执行效率更高的办法.要学的还有很多,要沉下心耐心学习.

using System;

class Program
{
    static void Main(string[] args)
    {
        string line;
        while (true)
        {
            line = Console.ReadLine();
            if (string.IsNullOrEmpty(line)) break;
            int n = Convert.ToInt32(line);
            int i;//循环控制变量
            int[] s = new int[n];//模拟环


            for (i = 0; i < n; i++)
            {

                s[i] = 1;//环初始化，=1表示没有吃，=0表示被吃了
            }
            i = 0;//从第一个人开始吃
            s[i] = 0; //第一个被吃掉
            
            
            for (int j = 0; j < n - 1; j++)//循环n-1，找出n-1个被吃的人
            {
                int count = 0;//每隔一个吃人的计数器
                while (true) //死循环找没被吃的人
                {
                    if (s[i] > 0)//这个人还没被吃
                    {
                        count++;//隔一个的计数器+1
                        if (count == 2) break;//找到隔一个的人
                    }
                    i = (i + 1) % n;//找到下一个人，由模除组成环
                    Console.WriteLine(i);
                }
                s[i] = 0; //这个人被吃掉
                Console.WriteLine("-------------");
            }
            
            
            
            Console.WriteLine(i + 1);//输出最后一个人，从1计数，比下标大1


        }
    }
}

这个算法的亮点在

i = (i + 1) % n;//找到下一个人，由模除组成环

利用mod来形成循环。。。。