【转载】找出不同的硬币

题目非常难！！！

我先给答案

using CP;

int nbTrials=4;
range trials=1..nbTrials;

int n=11;
range coins=1..n;

tuple comb // the light ones
{
int x;
int y;
}

{comb} combs={<i,j> | ordered i,j in coins}; // i and j are the bad coins

dvar boolean x[trials][coins][1..2]; // 4 trials n coins right and left side

dvar int y[combs][trials] in -1..1; // result of the weight -1 : less 0 : equal 1 : more


subject to
{
// same number of coins both side

forall(i in trials) sum(j in coins) x[i][j][1]==sum(j in coins) x[i][j][2];

// a coin is either left or right or not there

forall(i in trials) forall(j in coins) x[i][j][1]+x[i][j][2]<=1;

// not empty
forall(i in trials) sum(j in coins) x[i][j][1]!=0;

// results of the balance
forall(c in combs) 
	forall(i in trials) 
		y[c][i]
		==
		sgn(x[i][c.x][1]+x[i][c.y][1]-x[i][c.x][2]-x[i][c.y][2]);

// To be able to find the fraud
forall(ordered c1,c2 in combs) or(i in trials) (y[c1][i]!=y[c2][i]);

}

execute
{
function display(v)
{
return String.fromCharCode(64+v);
}

for(i in trials)
{
  for(var j in coins) if (x[i][j][1]==1) write(display(j));
  write("-");
  for(var j in coins) if (x[i][j][2]==1) write(display(j));
  writeln();
}
}

ABC-DEF BEH-CDJ DGH-EIJ AGI-FHJ and ABC-DEF DGH-EIJ AGI-BHJ CDEHI-ABFGJ

不知道这两枚是轻是重，一共有 110 种情况，天平称 4 次只能覆盖 81 种。。

@立紗Lisa #1 这是神的语言 Lisp？

@饱读书名 #3

$$ C_9^2 = 55 $$

不是110

又写错了

$ C_{11}^2$

写错了

$ C_11^2 = 55 $

@张怀义 #5 那两枚比别的轻是 55，比别的重又是 55。

不过我在 3 楼说的四次称只覆盖 81 种也不对，因为根据前一次称得不同的结果，下一次的称法可以不同。

@饱读书名 #8 在我看来，比较轻和比较重不是一样么？

@张怀义 #9 举例：如果现在知道在三个硬币里有一枚有问题的硬币，只能再称一次。天平一边放一个，称得 A > B，不能再称了。这时你知道 AB 中是哪个有问题？

所以较轻和较重不同。

如果这题有答案，我至少得用两天才能用编程方法做出来。就不试了。

楼主的语言看不懂，但我无法想象用这么少的代码就能实现。

楼主能不能描述一下具体的称法？

@饱读书名 #10 你说的对

@饱读书名 #3 对不起，你说的对。原题目是说2枚比其他轻。是我的问题

@饱读书名 #11
11个硬币里选择2个硬币 C(11,2) = 55 种组合 每次使用天平，有<,=,>三种情况，使用4次，可以得到3^4次方，81种结果

根据信息论得知，通过可以设计一种编码方式，实现用一个3进制的数来表示对应的一个组合

用枚举的方式去找到这个对应关系。 我贴的代码，就是在用枚举的办法，遍历去找这个对应关系。 具体由两种方案编码

方案1

ABC-DEF

BEH-CDJ

DGH-EIJ

AGI-FHJ

方案2

ABC-DEF

DGH-EIJ

AGI-BHJ

CDEHI-ABFGJ @小二 #4

这个是IBM自己研发的编程语言，类似LINGO

execute 这个关键字 ，类似 main函数

subject to 这个表示设定限制条件

不知道你学过线性优化没有

y < 7*x + 3 （1）

y < 8*x + 20 （2）

求y的最大值

subject to 类似 条件1，2

execute 相当于求y的最大值