现有题号称爱因斯坦出的智力题全世界只有2%能够做出。
------------------------------------------------
1、在一条街上,有5座房子,喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料,抽不同品牌的香烟,养不同的宠物
问题是:谁养鱼?
提示:
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、 挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
---------------------------------------
这里我想讲的是通过暴力算法穷举所有可能让计算机进行求解。
第一次试验使用“纯暴力”解法。问题规模达到(5!=120)5次幂,大于10G。本人花了将近30分钟运行,计算机依然没有算出结果。估计就是算一天也未必能结束。
于是在第二次试验中该进算法,通过使用类似逻辑中“短路”(如:a&&b&&c当a为假时b,c可以不需要计算结果也为假)的生成算法瞬间即可得到结果。
结论:
在这次经历中,我既感到通过写程序解决实际问题带来的快乐也进一步感受了算法的重要性。好的算法带来的效率是十分可观的。
说明:
1根据试验第四句话的左临意思包括相邻,否则解不惟一。
ProTable.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace SolvePuzzle
{
enum 国籍{英国,瑞典,丹麦,挪威,德国};
enum 颜色 {红,绿,蓝,黄,白};
enum 宠物 { 鸟,猫,马,鱼,狗};
enum 饮料 {水,牛奶,咖啡,茶,啤酒};
enum 香烟 { blends,blue,prince,dunhill,pall};
public class ProTable
{
private const string rule = @"
1、在一条街上,有5座房子,喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料,抽不同品牌的香烟,养不同的宠物
问题是:谁养鱼?
提示:
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、 挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
";
public string Rule { get { return rule; } }
private enum T{国籍=0,颜色,宠物,饮料,香烟};
private const int N = 5;
//求排列
private static int[,] aid = new int[120, N];
static ProTable()
{
int k = 0;
for (int i0 = 0; i0 < N; i0++)
{
for (int i1 = 0; i1 < N; i1++)
{
if (i1 == i0) continue;
for (int i2 = 0; i2 < N; i2++)
{
if (i2 == i1 || i2 == i0) continue;
for (int i3 = 0; i3 < N; i3++)
{
if (i3 == i2 || i3 == i1 || i3 == i0) continue;
for (int i4 = 0; i4 < N; i4++)
{
if (i4 == i3 || i4 == i2 || i4 == i1 || i4 == i0) continue;
aid[k, 0] = i0;
aid[k, 1] = i1;
aid[k, 2] = i2;
aid[k, 3] = i3;
aid[k, 4] = i4;
k++;
}
}
}
}
}
}
//判断矩阵
// 国籍,颜色,宠物,饮料,香烟
//1
//2
//3
//4
//5
private int[,] array = new int[N, N];
//根据排列数组生成
private void replace(int i,int j)
{
for (int k = 0; k < N; k++)
{
array[k, i] = aid[j, k];
}
}
//通过getXX得到相应的行号
private int get香烟(香烟 n)
{
for (int i = 0; i < array.Length; i++)
if (array[i, (int)T.香烟] == (int)n)
return i;
return -1;
}
private int get饮料(饮料 n)
{
for (int i = 0; i < array.Length; i++)
if (array[i, (int)T.饮料] == (int)n)
return i;
return -1;
}
private int get宠物(宠物 n)
{
for (int i = 0; i < array.Length; i++)
if (array[i, (int)T.宠物] == (int)n)
return i;
return -1;
}
private int get国籍(国籍 n)
{
for (int i = 0; i < array.Length; i++)
if (array[i, (int)T.国籍] == (int)n)
return i;
return -1;
}
private int get颜色(颜色 n)
{
for (int i = 0; i < array.Length; i++)
if (array[i, (int)T.颜色] == (int)n)
return i;
return -1;
}
//规则:
//1、英国人住红色房子
//2、瑞典人养狗
//3、丹麦人喝茶
//4、绿色房子在白色房子左面
//5、绿色房子主人喝咖啡
//6、抽Pall Mall 香烟的人养鸟
//7、黄色房子主人抽Dunhill 香烟
//8、住在中间房子的人喝牛奶
//9、 挪威人住第一间房
//10、抽Blends香烟的人住在养猫的人隔壁
//11、养马的人住抽Dunhill 香烟的人隔壁
//12、抽Blue Master的人喝啤酒
//13、德国人抽Prince香烟
//14、挪威人住蓝色房子隔壁
//15、抽Blends香烟的人有一个喝水的邻居
//1、英国人住红色房子
private bool assert1()
{
if (!(
array[get国籍(国籍.英国), (int)T.颜色] == (int)颜色.红
))
return false;
return true;
}
//2、瑞典人养狗
private bool assert2()
{
if (!(
array[get国籍(国籍.瑞典), (int)T.宠物] == (int)宠物.狗
))
return false;
return true;
}
//3、丹麦人喝茶
private bool assert3()
{
if (!(
array[get国籍(国籍.丹麦), (int)T.饮料] == (int)饮料.茶
))
return false;
return true;
}
//4、绿色房子在白色房子左面
private bool assert4()
{
if (!(
get颜色(颜色.绿) == (get颜色(颜色.白) - 1) //另一种理解get颜色(颜色.绿) < get颜色(颜色.白)
))
return false;
return true;
}
//5、绿色房子主人喝咖啡
private bool assert5()
{
if (!(
array[get颜色(颜色.绿), (int)T.饮料] == (int)饮料.咖啡
))
return false;
return true;
}
//6、抽Pall Mall 香烟的人养鸟
private bool assert6()
{
if (!(
array[get香烟(香烟.pall), (int)T.宠物] == (int)宠物.鸟
))
return false;
return true;
}
//7、黄色房子主人抽Dunhill 香烟
private bool assert7()
{
if (!(
array[get颜色(颜色.黄), (int)T.香烟] == (int)香烟.dunhill
))
return false;
return true;
}
//8、住在中间房子的人喝牛奶
private bool assert8()
{
if (!(
array[2, (int)T.饮料] == (int)饮料.牛奶
))
return false;
return true;
}
//9、 挪威人住第一间房
private bool assert9()
{
int i = get国籍(国籍.挪威);
if (!(
i== 0||i==4
))
return false;
return true;
}
//10、抽Blends香烟的人住在养猫的人隔壁
private bool assert10()
{
int t1 = get香烟(香烟.blends), t2 = get宠物(宠物.猫);
if (!(
t1 == (t2 + 1) || t1 == (t2 - 1)
))
return false;
return true;
}
//11、养马的人住抽Dunhill 香烟的人隔壁
private bool assert11()
{
int t1 = get宠物(宠物.马);
int t2 = get香烟(香烟.dunhill);
if (!(
t1 == (t2 + 1) || t1 == (t2 - 1)
))
return false;
return true;
}
//12、抽Blue Master的人喝啤酒
private bool assert12()
{
if (!(
array[get香烟(香烟.blue), (int)T.饮料] == (int)饮料.啤酒
))
return false;
return true;
}
//13、德国人抽Prince香烟
private bool assert13()
{
if (!(
array[get国籍(国籍.德国), (int)T.香烟] == (int)香烟.prince
))
return false;
return true;
}
//14、挪威人住蓝色房子隔壁
private bool assert14()
{
int t1 = get国籍(国籍.挪威);
int t2 = get颜色(颜色.蓝);
if (!(
t1 == (t2 + 1) || t1 == (t2 - 1)
))
return false;
return true;
}
//15、抽Blends香烟的人有一个喝水的邻居
private bool assert15()
{
int t1 = get香烟(香烟.blends);
int t2 = get饮料(饮料.水);
if (!(
t1 == (t2 + 1) || t1 == (t2 - 1)
))
return false;
return true;
}
private bool assert()
{
return assert1() && assert2() && assert3() && assert4() && assert5() && assert6() && assert7() && assert8() && assert9() &&
assert10() && assert11() && assert12() && assert13() && assert14() && assert15();
}
/*纯暴力算法以作比较
public void Solve_()
{
for (int i0 = 0; i0 < aid.GetUpperBound(0); i0++)
{
replace(0, i0);
for (int i1 = 0; i1 < aid.GetUpperBound(0); i1++)
{
replace(1, i1);
for (int i2 = 0; i2 < aid.GetUpperBound(0); i2++)
{
replace(2, i2);
for (int i3 = 0; i3 < aid.GetUpperBound(0); i3++)
{
replace(3, i3);
for (int i4 = 0; i4 < aid.GetUpperBound(0); i4++)
{
replace(4, i4);
if (assert())
{
Console.WriteLine(this);
}
}
}
}
}
}
}
*/
public void Solve()
{
//解号
int sn = 1;
//逐步生成判别表的算法
for (int i0 = 0; i0 < aid.GetUpperBound(0); i0++)
{
replace((int)T.国籍, i0);
if (!assert9())
continue;
for (int i1 = 0; i1 < aid.GetUpperBound(0); i1++)
{
replace((int)T.饮料, i1);
if (!assert8())
continue;
if (!(assert3()))
continue;
for (int i2 = 0; i2 < aid.GetUpperBound(0); i2++)
{
replace((int)T.颜色, i2);
if (!assert4())
continue;
if (!(assert1() && assert14()&&assert5()))
continue;
for (int i3 = 0; i3 < aid.GetUpperBound(0); i3++)
{
replace((int)T.宠物, i3);
if (!(assert2()))
continue;
for (int i4 = 0; i4 < aid.GetUpperBound(0); i4++)
{
replace((int)T.香烟, i4);
if (!(assert6() && assert7() && assert10() && assert11() && assert12() && assert15() && assert13()))
continue;
if (assert())
{
Console.WriteLine("解:"+sn++);
Console.WriteLine(this);
}
}
}
}
}
}
}
//国籍=0,颜色,宠物,饮料,香烟
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++)
{
sb.Append((i+1).ToString()+": ");
sb.Append(Enum.GetName(typeof(国籍),array[i,(int)T.国籍])+", ");
sb.Append(Enum.GetName(typeof(颜色), array[i, (int)T.颜色]) + ", ");
sb.Append(Enum.GetName(typeof(宠物), array[i, (int)T.宠物]) + ", ");
sb.Append(Enum.GetName(typeof(饮料), array[i, (int)T.饮料]) + ", ");
sb.Append(Enum.GetName(typeof(香烟), array[i, (int)T.香烟]) + "\n");
}
return sb.ToString();
}
}
}
-------------------------
Program.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace SolvePuzzle
{
class Program
{
static void Main(string[] args)
{
ProTable t = new ProTable();
t.Solve();
}
}
}
分享到:
相关推荐
C#笔试题大全C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.,让你...
c#,。net笔试题c#笔试题,包括选择题,概念题,解答题,答案。还,,net部分
c#,.net 程序员常见面试题大全(含答案) 程序员求职前的必不可少的准备工夫。
C# 面试题 更新 C#面试题 更新C#面试题 更新C#面试题 更新C#面试题
WPF设计的界面实在让人惊叹,有兴趣可以下载看看,包括源码和可执行程序,需要.NET3.0运行库以上支持,程序特点在于界面,代码部分没有刻意处理,包括对自定义标题栏的处理,开发工具:Visual C# 2008 Express,...
常见的C#面试题常见的C#面试题常见的C#面试题常见的C#面试题常见的C#面试题常见的C#面试题常见的C#面试题
C#基础面试题C#基础面试题C#基础面试题C#基础面试题C#基础面试题C#基础面试题C#基础面试题C#基础面试题
用C#实现的解线性方程组,程序用到Gauss消元法,动态添加文本框控件,并生成文本框矩阵(在此感谢CSDN网友帮我解决动态添加文本框控件这个问题)。一起上传的还有一张Gauss消元算法的PPT
很好的C#基础练习,不要错过
(1)编程输出1到100中能被3整除但不能被5整除的数,并统计有多少个这样的数。 (2)创建一个控制台应用程序,编写一个函数将十进制数转换成二进制数。程序可以 让用户一直进行转换,直到输入0为止。...
c# 解压缩文件或文件夹代码 c# 解压缩文件或文件夹代码 可设置压缩密码
个人整理的多家.Net开发面试题,包括类和结构的区别,死锁的必要条件,接口是否可以继承接口,构造器,final,finally,finallize的区别,C#中委托,进程和线程
C# 面向对象绝好的练习题C# 面向对象绝好的练习题C# 面向对象绝好的练习题C# 面向对象绝好的练习题C# 面向对象绝好的练习题C# 面向对象绝好的练习题C# 面向对象绝好的练习题C# 面向对象绝好的练习题
C# C# C# C# C# C# C# C# 适合初学者
aspose.words 16.7.0 for C# 破解版,.net 2.0 以上都可以使用,可能因为是破解版的原因,下载后会误报病毒,请放心所用。
C#练习题,总共60道,适合初学者。题不多,但都是经典的,容易疏忽的。
C# .net 面试题集合.rar C# .net 面试题集合.rar C# .net 面试题集合.rar C# .net 面试题集合.rar C# .net 面试题集合.rar C# .net 面试题集合.rar、 C# .net 面试题集合.rar C# .net 面试题集合.rar
操作简单方便,速度很快,适合简单计算三元一次方程组,必须是有三个方程式。我在做题的时候临时做的,希望大家喜欢。
C#做的自动更新word表、图题注插件(附源码) 插件具体说明: word插件:用来生成需要更新的word插件,除了自动更新题注,还提供自定义删除内容(根据word的页码). 插件xp安装环境:.net3.5、vsto、office2007 win7...
C#基础编程练习题,其中包括在VS2010中实现的详细代码,可以参考下