一道 面试算法题

Question

//Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些
  //人参加了竞赛：
  // （１）Ａ参加时，Ｂ也参加；
  // （２）Ｂ和Ｃ只有一个人参加；
  // （３）Ｃ和Ｄ或者都参加，或者都不参加；
  // （４）Ｄ和Ｅ中至少有一个人参加；
  // （５）如果Ｅ参加，那么Ａ和Ｄ也都参加
网上有两个答案，但认为这个答案要好一些
因为它更多是应用面向对象的方法，但下面的代码有问题 ，也有几名看不懂，请高人帮改正一下！class Program2
{
    static void Main(string[] args)
    {
        student[] stu =
        { 
            new student("A"),
            new student("B"),
            new student("C"),
            new student("D"),
            new student("E")
        };
        games(stu);
        for (int i = 0; i < stu.Length; i++)
        {
            Console.Write(stu[i].name);
            if (stu[i].join)
            Console.WriteLine("去了");
            else
            Console.WriteLine("没去");
        }
    }
    static void games(student[] stu)
    {
        if (stu[0].join)
        stu[1].join = true;        if (stu[1].join)
        stu[2].join = false;
        else
        stu[2].join = true;        stu[3].join = stu[2].join;        if (!stu[3].join)
        stu[4].join = true;        if (stu[4].join)
        {
            if (stu[0].join && stu[3].join)
            return;
            else   // 为什么要写下面两行
            {
                stu[0].join = false;
                games(stu);
            }
        }
    }
}

Answer 1

我觉得是刚调用games(stu);时只判断了A去的情况，而没有考虑A没去的情况，在stu[0].join = false;在递归调用之前将A设为不去的情况，再次进行上述过程。
不知这样理解对不？

Answer 2

A不用去,A去了,这个代码就是无限递归了.因为A去了,B肯定要去,B去了,C就不能去,C不能去,D也不能去,而D,E中至少去一个,那么E就必须去,跟后面的Ｅ去，那么Ａ和Ｄ也都去 ,直接起冲突,所以,A是不能去的.写这个代码的人在头脑中粗略推算出了A是肯定不去的.其实下面这一段没有任何意义,因为设定A不去的时候永远不会过,设定A去的时候就是直接无限递归导致堆栈溢出:  else   // 为什么要写下面两行
            {
                stu[0].join = false;
                games(stu);
            }结果:(人脑)
A,B,C,D,E
0,0,1,1,0还可以取位进行穷举的.
00000->11111

Answer 3

这个是利用二进制来标记ABCDE => 00000 然后历遍所有组合的例子using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;namespace ConsoleApplication
{
    class Program
    {
        static List<Student> Students = new List<Student>();
        const int MAX_COUNT = 31;
        const int LENGTH = 5;
        static void Main(string[] args)
        {
            Students.Add(new Student("A"));
            Students.Add(new Student("B"));
            Students.Add(new Student("C"));
            Students.Add(new Student("D"));
            Students.Add(new Student("E"));            for (int i = 0; i < MAX_COUNT; i++)
            {
                //00000000( 十进制 0) --> 00011111 ( 十进制 31) 取 5码
                for (int j = 0; j < LENGTH; j++)
                {
                    Students[j].Join = GetBinaryString(
                                                    Convert.ToString(i, 2)
                                                    )[7 - j] == '1' ? true : false;
                }
                FindStudents(Students);
            }
            Console.ReadKey();
        }        static char[] GetBinaryString(string s)
        {
            switch (s.Length)
            {
                case 1: s = "0000000" + s; break;
                case 2: s = "000000" + s; break;
                case 3: s = "00000" + s; break;
                case 4: s = "0000" + s; break;
                case 5: s = "000" + s; break;
                case 6: s = "00" + s; break;
                case 7: s = "0" + s; break;
            }
            return s.ToCharArray();
        }        static void FindStudents(List<Student> s)
        {
            //（１）Ａ参加时，Ｂ也参加；
            if (s[0].Join && !s[1].Join) return;            //（２）Ｂ和Ｃ只有一个人参加；
            if ((s[1].Join && s[2].Join) | (!s[1].Join && !s[2].Join)) return;            //（３）Ｃ和Ｄ或者都参加，或者都不参加；
            if ((s[2].Join && !s[3].Join) | (!s[2].Join && s[3].Join)) return;            //（４）Ｄ和Ｅ中至少有一个人参加；
            if ((!s[3].Join && !s[4].Join)) return;            //（５）如果Ｅ参加，那么Ａ和Ｄ也都参加;
            if (s[4].Join)
            {
                if (!(s[0].Join && s[3].Join)) return;
            }            //显示结果
            var Result = from o in s
                         select new { Msg = o.Name + (o.Join == true ? "去了" : "没去") };
            Console.WriteLine("======我是分割线======");
            foreach (var r in Result)
            {
                Console.WriteLine(r.Msg);
            }
        }
    }    class Student
    {
        public string Name { get; set; }
        public bool Join { get; set; }
        public Student(string Name)
        {
            this.Name = Name;
        }
    }
}