面试归来，被一个小学的奥赛题放倒//高手请进，我也不知道为什么不能给分。。
题目是这样的：先在纸上用一笔画出一个五角星，然后在五角星的5个角上和内部交叉点上分别画上圆圈。也就是一共10个圆圈。从1-10这10个数中不能重复的填入到这10个圈里，使得这个五角星上的五个三角形上的数字相加的值都等与16
先写出答案，然后编程实现。
俺没有做出来
我哭啊。。。。
问题点数：0、回复次数：129Top
1 楼tgj1202（tt）回复于 2006-05-28 14:45:04 得分 0
五角星要在程序里出现还是只是实现结果的数据结构呀。就是做填数字的算法就可以了呀。Top
2 楼ongzi（）回复于 2006-05-28 14:53:22 得分 0
我连答案都没写出来
Top
3 楼laiwusheng（风清扬）回复于 2006-05-28 14:54:35 得分 0
用计算机解这么一个线性方程组：（1<=ai,bi<=10&&ai!=bi）
a1+0 +0 +0 +0 +b1+b2+0 +0 +0 =16
0 +a2+0 +0 +0 +0 +b2+b3+0 +0 =16
0 +0 +a3+0 +0 +0 +0 +b3+b4+0 =16
0 +0 +0 +a4+0 +0 +0 +0 +b4+b5=16
0 +0 +0 +0 +a5 +b1+0 +0 +0 +b5=16
Top
4 楼laiwusheng（风清扬）回复于 2006-05-28 14:55:27 得分 0
有多组解Top
5 楼ongzi（）回复于 2006-05-28 15:13:03 得分 0
不是很明白，你能解释一下吗Top
6 楼sharpdew（风刃）回复于 2006-05-28 15:51:49 得分 0
1。先把16写为1－10个数中3个数的和，这样的组合容易写，才9组；
2。然后在这些组合中任意去5组合看是否满足上面的条件约束，因为已经是从16分解开的因子，所以和为16的条件已经满足了，然后选取的组合还要满足全部使用了10个数字，并且有且只有5个数字被重复使用了一次。
根据上述方法，很容易找到答案
Top
7 楼sharpdew（风刃）回复于 2006-05-28 15:56:11 得分 0
上面的不够完整，重写一下：
1。先把16写为1－10个数中3个数的和，这样的组合容易写，才9组；
2。然后在这些组合中任意取5组合看是否满足上面的条件约束，因为已经是从16分解开的因子，所以和为16的条件已经满足了；选取的组合还要满足全部使用了10个数字，并且有且只有5个数字被重复使用了一次；每个组合满足包含且只包含两个被重复使用的数字。
根据上述方法，很容易找到答案
Top
8 楼Z_Wing（）回复于 2006-05-28 16:02:07 得分 0
晕，面试这个也难了点吧。3楼思路正确，把题目具体成矩阵形式如下：
设五角星内部交叉的5个点上的数为x1,x2,x3,x4,x5。五个角上的数字为y1,y2,y3,y4,y5。根据题意列出方程为：
x1 + y1 + x2 = 16
x2 + y2 + x3 = 16
x3 + y3 + x4 = 16
x4 + y4 + x5 = 16
x5 + y5 + x1 = 16
(整理可得三楼的形式）
设向量X = [x1,x2,x3,x4,x5]（转置）,向量Y = [y1,y2,y3,y4,y5]（转置）,向量b ＝ [16,16,16,16,16](转置）
设矩阵A = {1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 0 1 1
1 0 0 0 1}
单位矩阵E ={1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1}
故原方程组为：EY + AX = b
这是个超越方程，好像使用最小二乘法解的（hoho，《矩阵理论》没学好啊），但要怎么写成程序呢？mark一个，召唤数学和程序达人解答。
面试考这个也难了点吧，楼主申请的是算法工程师？
Top
9 楼sharpdew（风刃）回复于 2006-05-28 16:08:55 得分 0
呵呵，我不相信小学生会用最小二乘法，不要把问题想那么复杂Top
10 楼sharpdew（风刃）回复于 2006-05-28 16:14:26 得分 0
按我上面的方法，很快就可以找出一组解：
1 5 10
1 7 8
2 5 9
2 6 8
3 6 7Top
11 楼sharpdew（风刃）回复于 2006-05-28 16:18:06 得分 0
实际上，分解16为3个数的和后，得到的是3类大的组合，每类中包含3个组合，选取的办法是从其中两个类中分别取两个组合，从剩下的一个类中取1个组合，这样的取法并不多，然后按我上面的条件进行判断即可。Top
12 楼laiwusheng（风清扬）回复于 2006-05-28 16:31:03 得分 0
A={a1,a2,a3,a4,a5};B={b1,b2,b3,b4,b5};
A= {a1 0 0 0 0
0 a2 0 0 0
0 0 a3 0 0
0 0 0 a4 0
0 0 0 0 a5 }
B= {b1 b2 0 0 0
0 b2 b3 0 0
0 0 b3 b4 0
0 0 0 b4 b5
b1 0 0 0 b5 }
(A,B)X=(16,16,16,16,16)
解这方程很简单吧，数值分析里都学过
这里我收藏了一个算法，把系数写进主函数去就行了：
#include "stdlib.h"
#include "stdio.h"
int cjordn(n,ar,ai,m,br,bi)
int n,m;
double ar[],ai[],br[],bi[];
{ int *js,l,k,i,j,is,u,v;
double p,q,s,d;
js=malloc(n*sizeof(int));
for (k=0;k<=n-1;k++)
{ d=0.0;
for (i=k;i<=n-1;i++)
for (j=k;j<=n-1;j++)
{ u=i*n+j;
p=ar[u]*ar[u]+ai[u]*ai[u];
if (p>d) {d=p;js[k]=j;is=i;}
}
if (d+1.0==1.0)
{ free(js); printf("err**fail\n");
return(0);
}
if (is!=k)
{ for (j=k;j<=n-1;j++)
{ u=k*n+j; v=is*n+j;
p=ar[u]; ar[u]=ar[v]; ar[v]=p;
p=ai[u]; ai[u]=ai[v]; ai[v]=p;
}
for (j=0;j<=m-1;j++)
{ u=k*m+j; v=is*m+j;
p=br[u]; br[u]=br[v]; br[v]=p;
p=bi[u]; bi[u]=bi[v]; bi[v]=p;
}
}
if (js[k]!=k)
for (i=0;i<=n-1;i++)
{ u=i*n+k; v=i*n+js[k];
p=ar[u]; ar[u]=ar[v]; ar[v]=p;
p=ai[u]; ai[u]=ai[v]; ai[v]=p;
}
v=k*n+k;
for (j=k+1;j<=n-1;j++)
{ u=k*n+j;
p=ar[u]*ar[v]; q=-ai[u]*ai[v];
s=(ar[v]-ai[v])*(ar[u]+ai[u]);
ar[u]=(p-q)/d; ai[u]=(s-p-q)/d;
}
for (j=0;j<=m-1;j++)
{ u=k*m+j;
p=br[u]*ar[v]; q=-bi[u]*ai[v];
s=(ar[v]-ai[v])*(br[u]+bi[u]);
br[u]=(p-q)/d; bi[u]=(s-p-q)/d;
}
for (i=0;i<=n-1;i++)
if (i!=k)
{ u=i*n+k;
for (j=k+1;j<=n-1;j++)
{ v=k*n+j; l=i*n+j;
p=ar[u]*ar[v]; q=ai[u]*ai[v];
s=(ar[u]+ai[u])*(ar[v]+ai[v]);
ar[l]=ar[l]-p+q;
ai[l]=ai[l]-s+p+q;
}
for (j=0;j<=m-1;j++)
{ l=i*m+j; v=k*m+j;
p=ar[u]*br[v]; q=ai[u]*bi[v];
s=(ar[u]+ai[u])*(br[v]+bi[v]);
br[l]=br[l]-p+q; bi[l]=bi[l]-s+p+q;
}
}
}
for (k=n-1;k>=0;k--)
if (js[k]!=k)
for (j=0;j<=m-1;j++)
{ u=k*m+j;v=js[k]*m+j;
p=br[u]; br[u]=br[v]; br[v]=p;
p=bi[u]; bi[u]=bi[v]; bi[v]=p;
}
free(js);
return(1);
}
Top
13 楼laiwusheng（风清扬）回复于 2006-05-28 16:43:22 得分 0
系数弄错了, Z_Wing() 的正确！
改……
Top
14 楼crazy_lazy_pig（疯狂懒猪）回复于 2006-05-28 17:09:29 得分 0
哪五个三角形啊? 我怎么看到了10个?Top
15 楼Z_Wing（）回复于 2006-05-28 19:37:06 得分 0
对，是我想复杂了，既然在10以内，可以直接用sharpdew说的方法，把答案斗出来。
大家帮我看看这个程序，主程序穷举出满足条件的组合，但我的check函数做筛选怎么不起作用呢，哪儿错了呢？
#include <stdio.h>
#define TURE 1
#define FALSE 0
typedef unsigned int Bool;
//存满足条件的结果
struct equalmum
{
int x;
int y;
int z;
}ret[1000];
Bool check(int x,int y,int z)
{
int i;
for (i = 0;i < 1000;i ++)
{
if ((ret[i].x == y || ret[i].x == z) && (ret[i].y == x || ret[i].y == z) && (ret[i].z == x || ret[i].z == y))
return FALSE;
}
return TURE;
}
int main()
{
int x,y,z;
int i,j,k;
int index = 0;
for (i = 0;i < 1000;i ++)
{
ret[i].x = 0;
ret[i].y = 0;
ret[i].z = 0;
}
for (i = 1;i < 11;i++)
{
x = i;
for (j = 1;j < 11;j++)
{
if (j != x)
y = j;
else
continue;
for (k = 1;k < 11;k++)
{
if (k !=x && k != y)
z = k;
else
continue;
if (x + y + k == 16 && check(x,y,z))
{
ret[index++].x = x;
ret[index++].y = y;
ret[index++].z = z;
printf("x=%d,y=%d,z=%d\n",x,y,z);
}
}
}
}
return 0;
}Top
16 楼SAMUEL_NAME（）回复于 2006-05-29 00:19:09 得分 0
16是一个偶数
要三个数的和相加等于偶数的话，那么其中一定有偶数个奇数。即0个或2个奇数
按照以上的思路很快可以确定，在内层的数字只有可能是1，3，5，7，9
然后
1不能和3处在同一三角形，7和9不能在同一三角形，1和9若在同一三角形时，3和7一定不在同一三角形
就这样可以推出结果。
10
8 1 5 2
7 9
3
6 4
下面来研究如何编程…………：）Top
17 楼SAMUEL_NAME（）回复于 2006-05-29 00:23:57 得分 0
答案是唯一的
就是我上面给的那个答案Top
18 楼SAMUEL_NAME（）回复于 2006-05-29 02:42:42 得分 0
想不出来了…………………………
好难啊…………
MARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARK
Top
19 楼FengYuanMSFT（(6.4 被封杀)袁峰 http://fengyuancom.spaces.live.com）回复于 2006-05-29 06:14:36 得分 0
class CStar
{
int m_number[10]; // 5 outside, followed by 5 inside
public:
void solve(int depth)
{
if (depth == 10)
{
if ((m_number[0] + m_number[5] + m_number[9]) == 16)
{
for (int i = 0; i < 10; i ++)
{
printf("%d ", m_number[i]);
}
printf("\n");
}
}
else
{
for (int i = 1; i <= 10; i ++)
{
for (int j = 0; j < depth; j ++)
{
if (m_number[j] == i)
{
goto next;
}
}
if (depth >= 6)
{
if ((i + m_number[depth - 5] + m_number[depth - 1]) != 16)
{
goto next;
}
}
m_number[depth] = i;
solve(depth + 1);
next: ;
}
}
}
};
2 4 6 8 10 9 3 7 1 5
2 5 8 6 9 10 1 7 3 4
2 9 6 8 5 4 3 7 1 10
2 10 8 6 4 5 1 7 3 9
4 2 10 8 6 9 5 1 7 3
4 6 8 10 2 3 7 1 5 9
5 2 9 6 8 10 4 3 7 1
5 8 6 9 2 1 7 3 4 10
6 4 2 10 8 3 9 5 1 7
6 8 5 2 9 7 1 10 4 3
6 8 10 2 4 7 1 5 9 3
6 9 2 5 8 3 4 10 1 7
8 5 2 9 6 1 10 4 3 7
8 6 4 2 10 7 3 9 5 1
8 6 9 2 5 7 3 4 10 1
8 10 2 4 6 1 5 9 3 7
9 2 5 8 6 4 10 1 7 3
9 6 8 5 2 3 7 1 10 4
10 2 4 6 8 5 9 3 7 1
10 8 6 4 2 1 7 3 9 5Top
20 楼templarzq（原谅我这一生不羁放纵爱自由，也会怕有一天会跌倒）回复于 2006-05-29 10:31:33 得分 0
楼上能否解释一下？？Top
21 楼FengYuanMSFT（(6.4 被封杀)袁峰 http://fengyuancom.spaces.live.com）回复于 2006-05-29 11:09:58 得分 0
[0] 到 [4] 5 个角
[5] 到 [9] 5 个内部交叉点
[0] + [5] + [9] = 16
[1] + [6] + [5] = 16
[2] + [7] + [6] = 16
[3] + [8] + [7] = 16
[4] + [9] + [8] = 16
[i] + [i+5] + [(i+14) % 10] = 16
把 内部交叉点 放在 [0] 到 [4] 可以更快Top
22 楼templarzq（原谅我这一生不羁放纵爱自由，也会怕有一天会跌倒）回复于 2006-05-29 11:25:48 得分 0
穷举。。。Top
23 楼beatles89（求学者）回复于 2006-05-29 11:33:27 得分 0
是9组吗？我怎么能写出10组？
Top
24 楼zez（思恩 闭关练功ing...）回复于 2006-05-29 11:47:39 得分 0
最笨的方法..
穷举 你都不会么??
Top
25 楼dream2013（每个人都有魔鬼的一面( http://blog.sina.com.cn/u/1422260677 )）回复于 2006-05-29 12:36:26 得分 0
mark
回家看Top
26 楼justin108（如水如烟）回复于 2006-05-29 12:43:39 得分 0
哞Top
27 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2006-05-29 13:25:15 得分 0
穷举的话复杂度也不大的.....,思想还直接一些Top
28 楼xb90110（）回复于 2006-05-29 13:28:53 得分 0
图形怎么实现？？？Top
29 楼trunami_nb（海啸）回复于 2006-05-29 14:09:48 得分 0
只有四组答案，其他答案重复：
2 5 10 4 9 1 7 3 6 8
2 10 5 9 4 1 7 3 6 8
6 8 7 3 4 1 5 9 2 10
6 8 7 3 9 1 10 4 2 5
Top
30 楼trunami_nb（海啸）回复于 2006-05-29 14:20:21 得分 0
以上答案我是用枚举算法得出，摆列位置顺序为：
1
2 3 4 5
6 8
7
10 9Top
31 楼trunami_nb（海啸）回复于 2006-05-29 14:26:13 得分 0
按照先外后内，逆时针排列的答案如下：（四组答案）
5 2 9 6 8 1 10 4 3 7
8 6 4 2 10 1 7 3 9 5
8 6 9 2 5 1 7 3 4 10
10 2 4 6 8 1 5 9 3 7
Top
32 楼intereye（面朝大海，春暖花开）回复于 2006-05-29 14:32:48 得分 0
袁老大都来了~~学习了。Top
33 楼iamgsyy（兰州）回复于 2006-05-29 15:11:25 得分 0
好东东Top
34 楼canjianchangkong（残剑长空）回复于 2006-05-29 17:00:36 得分 0
窮舉出來十組，
1，5，10
1，6，9
1，7，8
2，4，10
2，5，9
2，6，8
3，4，9
3，5，8
3，6，7
4，5，7
要是快速做題的話，SAMUEL_NAME()的算法是最帥最帥的！！
奇數放中間，再排列一下偶數，這個算法！！真漂亮！
出題本意也應該如此，小學奧數。
要是編程實現，那就是窮舉了。
語句學習中……Top
35 楼donal_z（冬）回复于 2006-05-29 17:34:51 得分 0
to FengYuanMSFT
[i] + [i+5] + [(i+14) % 10] = 16
i=0时,(0+14)%10=4 //!=16Top
36 楼templarzq（原谅我这一生不羁放纵爱自由，也会怕有一天会跌倒）回复于 2006-05-29 17:55:40 得分 0
楼上的，人家已经把i=0的情况单列出来了Top
37 楼edp08（王二）回复于 2006-05-29 17:59:56 得分 0
小学奥数，呵呵Top
38 楼maomaobao（）回复于 2006-05-29 18:07:56 得分 0
真是大开眼界阿！Top
39 楼pakix（pakix）回复于 2006-05-29 18:20:26 得分 0
yun a, only two result!!
10 only company with (2, 4) & (1, 5),
other has at least 3 companies
darw a graphic,
and check the odd-even property
then you can find only two combination exist!!
note:
zhe li you chong gen!!
>>回复人：trunami_nb(海啸) ( 一级(初级)) 信誉：100 2006-05-29 14:26:00 得分:0
>>
>>按照先外后内，逆时针排列的答案如下：（四组答案）
A>>5 2 9 6 8 1 10 4 3 7
B>>8 6 4 2 10 1 7 3 9 5
C>>8 6 9 2 5 1 7 3 4 10
D>>10 2 4 6 8 1 5 9 3 7
A == flip(C)
B == flip(D)
or:
C == flip(A)
D == flip(B)
Top
40 楼YFY（天易）回复于 2006-05-29 18:27:08 得分 0
我给我的小侄女做过，呵呵，不过没有用编程。Top
41 楼pakix（pakix）回复于 2006-05-29 18:31:23 得分 0
sorry,forgot another equaltion:
(sigma I[i]) == 25
(sigma O[i]) == 30
sigam:sum
I:inner
O:outerTop
42 楼Rozre（神灵）回复于 2006-05-29 18:38:22 得分 0
这个用矩阵做.很简单Top
43 楼scjpsz1860（友情UP友情接分)(快乐升星！预祝明天更好！:）回复于 2006-05-29 19:02:20 得分 0
MarkTop
44 楼leo2003（【健者天行】谁伴我闯荡）回复于 2006-05-29 20:10:42 得分 0
好强
Top
45 楼geguangping（）回复于 2006-05-29 20:13:43 得分 0
1、3、5、7、9在里层，2、4、6、8、10在外层。
5和6处在相对的位置。
6为头；
3、7为肩；
4、8为手；
9、1为腰；
2、10为脚；
5为丹田。Top
46 楼wizardblue（）回复于 2006-05-29 20:38:21 得分 0
我的dev c++老是启动以后死掉,用java写了一个
就用的dfs(深搜,O(10!)大约1e7的样子,勉强能够接受)
/*
先定义star(10)
在五角星上面的下标如下图所示分布
..................0...............
..................................
....1.........2.........3........4
..................................
..........6...............5.......
..................................
..................7...............
..................................
....9...........................10
*/
public class Star {
static int[][] small_triangle = new int[][] { new int[] { 0, 2, 3 },
new int[] { 1, 2, 5 },
new int[] { 3, 4, 6 },
new int[] { 5, 7, 8 },
new int[] { 6, 7, 9 } };
static int[]tmp_triangle=new int[10];
static int solutions = 0;
static int []flag=new int[11];
static void show_star(int[] p){
System.out.println("-------- solution:"+(solutions+1)+" -------------");
System.out.println(".................."+p[0]+"...............");
System.out.println("..................................");
System.out.println("...."+p[1]+"........."+p[2]+"........."+p[3]+"........"+p[4]);
System.out.println("..................................");
System.out.println(".........."+p[5]+"..............."+p[6]+".......");
System.out.println("..................................");
System.out.println(".................."+p[7]+"...............");
System.out.println("..................................");
System.out.println("...."+p[8]+"..........................."+p[9]);
System.out.println();
}
static void dfs(int index){
if(index ==10){
int sum_count=0;
for(int i=0;i<5;i++){
int sum=0;
for(int j=0;j<3;j++){
sum+=tmp_triangle[small_triangle[i][j]];
}
if(sum==16){
sum_count++;
}
}
if(sum_count==5){
show_star(tmp_triangle);
solutions++;
}
return ;
}
for(int i=1;i<11;i++){
if(flag[i]==0){
flag[i]=1;
tmp_triangle[index]=i;
dfs(index+1);
flag[i]=0;
}
}
}
public static void main(String[] args) {
dfs(0);
System.out.println("total solutions:"+solutions);
}
}
Top
47 楼mustlook（狮鹫拿着刀叉吃大餐）回复于 2006-05-29 23:30:16 得分 0
明天看Top
48 楼cattlenzq（吃狼的豆腐（不要给分了，散起来真麻烦！））回复于 2006-05-30 00:16:22 得分 0
日了，我一直想怎么能在 五角星内画10个圈。。。。。还不能重复。。。。。。。。。。。。。Top
49 楼gpuboy（3D梦工厂）回复于 2006-05-30 00:43:49 得分 0
回溯算法解决。over！Top
50 楼FengYuanMSFT（(6.4 被封杀)袁峰 http://fengyuancom.spaces.live.com）回复于 2006-05-30 02:24:44 得分 0
> [i] + [i+5] + [(i+14) % 10] = 16
> i=0时,(0+14)%10=4 //!=16
I meant: for (int i = 0; i < 5; i ++)
m_number[i] + m_number[i+5] + m_number[(i+14) % 10] == 16
Top
51 楼gpuboy（3D梦工厂）回复于 2006-05-30 02:42:42 得分 0
看错题了。我看成是求五角星的五条直线，其中每条直线上4个节点的和为16。
本人审题错误，罪过！罚自己明天不准喝咖啡。Top
52 楼kanshu123（初学者）回复于 2006-05-30 10:11:56 得分 0
MarkTop
53 楼oceannut（我家有只黑猫）回复于 2006-05-30 10:43:16 得分 0
本人比较笨，费了挺长时间，用最原始的方法推导:
首先5个三角之和都是16,那么总合是80.
1,2,3,4,5,6,7,8,9,10加起来的总合是55,还剩下25,也就是说在这个5个三角形中,每个数出现过一次以外(顶点上),还有5个数出现过两次(交叉点上),那么多出现一次的这5个数之和为25.
找出一个1,3,5,7,9数列:
4
3 9
6 2
7 5
1
8 10
就是:4+3+9=16,6+3+7=16,7+8+1=16,10+5+1=16,9+5+2=16Top
54 楼cityhunterhjj（）回复于 2006-05-30 11:41:50 得分 0
都是高手，学习的东西还有很多很多很多Top
55 楼lvmart（奋斗的蜗牛）回复于 2006-05-30 12:56:39 得分 0
我想了一个思路：
首先1－10的和为55，而5个小三角形每个的和为16，那么加起来为80，因为五角星的五个顶角只加过一次，而里面的角都是加过两次的，所以很快就可以算出来五个顶角的和为50，而里面五个角的和为25，这样就可以得出五个顶角为2,4,6,8,10,里面五个数为1,3,5,7,9.
然后考虑顶角上特殊的两个数，2和10。10要得到和为16，那么必须和1，5组合，所以10，1，5三个必须在一个三角形上，然后考虑2，2必须和5，9 组合，这样2，5，9必须在一个三角行上。
这样1，5，9的位置已经确定好了，只有3和7了，也只剩下两个位置了，3不可能和1在一个三角行内，所以整个数的位置就确定了。
至于编程应该不是很难了。Top
56 楼MagicianLiu（魔术师·刘）回复于 2006-05-30 16:18:29 得分 0
按照楼上的说法。。
1-10和为55，5×16＝80。因为中间的5个数加了2编。所以80-55为中间5个数之和。只要在1-10内找5个数和为25的就行了。。Top
57 楼luckyfreeball（）回复于 2006-05-30 18:15:58 得分 0
内环之和为25，25拆分为5个正数，当中肯定有奇数个奇数，也就是说25只可能拆出1/3/5个奇数
而一个三角形和为16，必有偶数个奇数，通过这2个条件可以判断出1不可能Top
58 楼tgj1202（tt）回复于 2006-05-30 19:28:59 得分 0
晕，先还以为是全部三角型，结果没有答案。发现是五个，用了一个很烂的方法算出了17组数据：
初学，庆祝...........
#include <stdio.h>
int compare (int a[],int x)
{
int i,j;
for (i=0;i<x;i++) {
for(j=i+1;j<x;j++) {
if (a[i]==a[j]) {
return 0;
}
}
}
return 1;
}
int main()
{
int answer[10];
int number = 0;
int a[10] = {1,1,1,1,1,1,1,1,1,1};
for (a[0]=1;a[0]<=10;a[0]++)
{
answer[0] = a[0];
for (a[1] = 1; a[1]<10 ;a[1]++)
{
answer[1] = a[1];
if(compare(answer,2))
{
for (a[2] = 1; a[2]<=10 ;a[2]++)
{
answer[2] = a[2];
if(compare(answer,3))
{
for (a[3] = 1; a[3]<=10 ;a[3]++)
{
answer[3] = a[3];
if(compare(answer,4))
{
for (a[4] = 1; a[4]<=10 ;a[4]++)
{
answer[4] = a[4];
if(compare(answer,5))
{
for (a[5] = 1; a[5]<=10 ;a[5]++)
{
answer[5] = a[5];
if(compare(answer,6))
{
for (a[6] = 1; a[6]<=10 ;a[6]++)
{
answer[6] = a[6];
if(compare(answer,7))
{
for (a[7] = 1; a[7]<=10 ;a[7]++)
{
answer[7] = a[7];
if(compare(answer,8))
{
for (a[8] = 1; a[8]<=10 ;a[8]++)
{
answer[8] = a[8];
if(compare(answer,9))
{
for (a[9] = 1; a[9]<=10 ;a[9]++)
{
answer[9] = a[9];
if(compare(answer,10))
{
if (answer[0]+answer[2]+answer[3] == 16 && answer[1]+answer[2]+answer[5] == 16 && answer[3]+answer[4]+answer[7] == 16 && answer[8]+answer[5]+answer[6] == 16 && answer[6]+answer[7]+answer[9] == 16)
{
int n = 0;
for (n=0; n<10; n++)
{
printf("a%d = %d \n",(n+1),answer[n]);
}
printf("the %d array\n",number);
number++;
}
}// if 10
}
} // if 9
}
}// if 8
}
}// if 7
}
}// if 6
}
}// if 5
}
}// if 4
}
}// if 3
}
}//if 2
}
}//for a[0]
printf("the over\n");
return 0;
}// gcc aa.c -o aa.exeTop
59 楼dragonpig（）回复于 2006-05-30 19:49:52 得分 0
大家的思维真是活跃啊。
去除循环，逆序一共两解。
从第一个凹点起，沿五角星外围顺序依次为
A：1 5 10 2 4 9 3 6 7 8
B：1 8 7 6 3 4 9 2 5 10
内圈有两种情况，全奇数和三奇二偶Top
60 楼SAMUEL_NAME（）回复于 2006-05-30 20:45:47 得分 0
好牛
MARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKMARKTop
61 楼caitian6（）回复于 2006-05-30 23:14:49 得分 0
学习Top
62 楼idcfly（应该躲哪去）回复于 2006-05-31 10:34:13 得分 0
学习Top
63 楼wuyazhe（wyz&xyl）回复于 2006-05-31 10:53:10 得分 0
upTop
64 楼rarexu（普通人）回复于 2006-05-31 11:27:16 得分 0
支持SAMUEL_NAME()
题目的原意就是只要一个答案就可以了
而且只有这种情况是小学生才可以完成的Top
65 楼benqmm（Blue Baby）回复于 2006-05-31 11:28:22 得分 0
学习Top
66 楼joneyonly（）回复于 2006-05-31 11:29:42 得分 0
markTop
67 楼zgh144（）回复于 2006-05-31 11:45:54 得分 0
大开眼见Top
68 楼djfu（飞龙在天）回复于 2006-05-31 12:55:46 得分 0
哈哈，楼主被人笔试(BS)了。Top
69 楼smnzg（过路人）回复于 2006-05-31 13:14:09 得分 0
MarkTop
70 楼xiao_fang（frank）回复于 2006-05-31 13:46:32 得分 0
思路：
设5个角上数值和为x, 内部交叉点数值和为y，则有：
x+y=55 ( 即1＋2＋...＋10=(1+10)*10/2=55 ）
内部交叉点上的数在参与5个三角形上数值计算时都会使用两次，而5个角上的数只使用一次，据此：
x+2y=16*5
解方程：
x=30
y=25
据此遍历1~10共10个数中所有组合（不多），得到符合条件的内、外5个数的组合，再根据这些组合进行遍历满足三角形和为16的组合。Top
71 楼laiwusheng（风清扬）回复于 2006-05-31 13:58:44 得分 0
思路很简单！
关键是如何 从1到10中求出和是25的五个数且不重复。Top
72 楼andylee245（）回复于 2006-05-31 14:22:00 得分 0
没有楼上的想的那么简单.Top
73 楼slipsun（奋斗!直到我的名字响彻天堂...）回复于 2006-05-31 14:48:06 得分 0
仙人真是多啊。。。Top
74 楼Bill1212（Bill）回复于 2006-05-31 16:55:13 得分 0
是道回朔法的题Top
75 楼tiewen（铁文）回复于 2006-05-31 17:00:16 得分 0
laiwusheng(萧剑) ( ) 信誉：100
用计算机解这么一个线性方程组：（1<=ai,bi<=10&&ai!=bi）
a1+0 +0 +0 +0 +b1+b2+0 +0 +0 =16
0 +a2+0 +0 +0 +0 +b2+b3+0 +0 =16
0 +0 +a3+0 +0 +0 +0 +b3+b4+0 =16
0 +0 +0 +a4+0 +0 +0 +0 +b4+b5=16
0 +0 +0 +0 +a5 +b1+0 +0 +0 +b5=16
有多组解，且解是对称的Top
76 楼xiongmao007（）回复于 2006-05-31 18:01:12 得分 0
这道题应该有一些关于编程的要求不然一点意思都没有。
究竟是用尽量简单的算法，还是用人脑多代替计算机思考？
有一位网友给的算法很简单，但却忽视了计算机的能动性。
还是要看要求。Top
77 楼manadream（睡在咪咪的咪咪上）回复于 2006-05-31 18:20:01 得分 0
这道题不简单，并且既然考这种题，不可能要你搞遍历
以下是我10分钟的成果，请拍砖。
1，证明内圈和25，外圈和30（不用解释了）
2，平均数为5，6。建立3个数组，两个奇数组，一个偶数组
3，证明只有两奇数，一偶可以满足条件(第一个16如果你用了3个偶，你后面怎么也搞不全了)
从而反证3个数组的合理性
4，建立数组索引，3个数组分别要一个索引号（避免奇数重复）
5，大家会发现，索引和为9。然后3个单维数组排他便利（为了提高效率，偶数从最大和最小排）
因为那样有唯一性。遍历到第四个的时候就好了，因为建立的数据模型必然保证了最后一个
是合理的。
先证明，然后写一个3数组（5个）的短遍历
就可以轻松搞定。
Top
78 楼SAMUEL_NAME（）回复于 2006-05-31 19:06:50 得分 0
回蒴法！ 真棒的名字
我那天研究怎么实现这个程序的时候就是在这里被难到了
必须回蒴
哪位高人给个回蒴的例子好不？
谢呀谢！谢呀谢！谢呀谢！谢呀谢！谢呀谢！
另……粽子节 && 儿童节快乐！Top
79 楼aupha（栀子迎风）回复于 2006-05-31 20:54:07 得分 0
小学奥赛都有这么难了？
我小学都没有读好。
学习....Top
80 楼Go_Rush（我的技术博客http://ashun.cnblogs.com/）回复于 2006-05-31 22:16:48 得分 0
大家都很牛，值得学习Top
81 楼bufan2162（永远保持前进状态）回复于 2006-05-31 22:52:43 得分 0
狂顶啊Top
82 楼yuyuxiaoyu（左大S,右小S,偶居中）回复于 2006-06-01 08:15:16 得分 0
被放倒了Top
83 楼98440622（民工++）回复于 2006-06-01 08:43:26 得分 0
考虑到内圈全部为奇数，于是问题转化为1,3,5,7,9序列使得相邻的两个数之和在4和16之间，于是回溯法找出所有解。
贴部分程序
struct _tagTriangle
{
int angle[3];
}triangle[5];
struct _tagElement
{
int value;
int used;
}elements[5];
....
for (i = 0; i < 5; i++)
{
elements[i].value = i * 2 + 1;
elements[i].used = 0;
}
...
i = 5;
j = 0;
while (1)
{
while (j < 5 && elements[i].used != 0) j++;
if (j >= 5)
{
i--;
j = pop();
if (j < 0)
break;
else
{
j /= 2;
elements[j].used = 0;
j++;
}
}
else
{
results[i] = element[j].value;
elements[j].used = 1;
push(results[i]);
j = 0;
i++;
if (i == 10)
{
for (k = 5; k < 9; k++)
if (results[k] + result[k + 1] <= 4
|| results[k] + result[k + 1] >= 16)
break;
if (k == 9
&& results[5] + result[9] > 4
&& results[5] + result[9] < 16)
{
count++;
printf("%d combination found\n", count);
PRINT(result);
}
}
}
}Top
84 楼FengYuanMSFT（(6.4 被封杀)袁峰 http://fengyuancom.spaces.live.com）回复于 2006-06-01 09:12:39 得分 0
> 考虑到内圈全部为奇数
Wrong assumptionTop
85 楼losedxyz（我真的一无所有）回复于 2006-06-01 09:32:18 得分 0
[0] 到 [4] 5 个角
[5] 到 [9] 5 个内部交叉点
[0] + [5] + [9] = 16
[1] + [6] + [5] = 16
[2] + [7] + [6] = 16
[3] + [8] + [7] = 16
[4] + [9] + [8] = 16
[i] + [i+5] + [(i+14) % 10] = 16
这个妙Top
86 楼pipilupzj（皮皮鲁）回复于 2006-06-01 09:35:19 得分 0
mark
有空再研究Top
87 楼hisi（海山)(随机种子）回复于 2006-06-01 10:28:37 得分 0
现在的小学生,真强..Top
88 楼yjl99（小妮）回复于 2006-06-01 11:32:41 得分 0
牛，有些做错了，呵呵Top
89 楼harborian（harbor）回复于 2006-06-01 12:06:41 得分 0
先说直观地给出答案：
1到10十个数的总和是55，而16*5=80，80-55=25。说明内圈总和为25，外圈总和为30。显见1，3，5，7，9的总和为25；2，4，6，8，10的总和为30。稍加排列就可得出答案。
再说用程序的方法：
先给出答案，奇数位置放在内部，偶数位置放在外圈顶点。
1 5 10 2 4 9 3 6 7 8
1 8 7 6 3 4 9 2 5 10
1 8 7 6 3 9 4 2 10 5
1 10 5 2 9 4 3 6 7 8
其中答案1和4，答案2和3是一个相反的顺序。
这实质是一个动态规划的问题。在那么短的时间，很难理清思路，又不是为竞赛参加过专门的训练:-)
这里我就不详细的分析了，这给出一种解题程序：
#include <vector>
#include <iostream>
using namespace std;
int Result[10];
void Find(int nIndex, int value, vector<int> vLeft)
{
Result[nIndex*2] = value;
if (vLeft.size() == 1)
{
if ((value + vLeft[0] + Result[0] == 16))
{
Result[nIndex*2+1] = vLeft[0];
for (int i=0; i<10; i++)
{
cout << Result[i] << ' ';
}
cout << endl;
}
return;
}
for (int i=0; i<vLeft.size(); i++)
{
for (int j=0; j<vLeft.size(); j++)
{
if (j == i)
continue;
if (value + vLeft[i] + vLeft[j] == 16)
{
vector<int> vTemp;
for (int k=0; k<vLeft.size(); k++)
{
if (k!=i && k!=j)
vTemp.push_back(vLeft[k]);
}
Result[nIndex*2+1] = vLeft[i];
Find(nIndex+1, vLeft[j], vTemp);
}
}
}
}
int main()
{
vector<int> vLeft(9);
for (int i=0; i<9; i++)
vLeft[i] = i+2;
Find(0, 1, vLeft);
}Top
90 楼TCat（蚊子）回复于 2006-06-01 12:35:18 得分 0
什么公司？这么个考法！！！Top
91 楼lengyuewuhen（飞雪）回复于 2006-06-01 12:57:37 得分 0
呵呵,这么多人啊
Top
92 楼liufeifei（）回复于 2006-06-01 13:23:48 得分 0
好象不难啊Top
93 楼mjk86（）回复于 2006-06-01 13:24:19 得分 0
manadream(睡在咪咪的咪咪上)
非常聪明啊，方法非常巧。
laiwusheng(萧剑)
非常直接，好，很棒啊。
Top
94 楼dongpy（51-->ARM）回复于 2006-06-01 13:36:51 得分 0
3，证明只有两奇数，一偶可以满足条件(第一个16如果你用了3个偶，你后面怎么也搞不全了)
从而反证3个数组的合理性
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这是个伪命题～Top
95 楼windy_wu2001（windy）回复于 2006-06-01 14:12:34 得分 0
16是一个偶数
要三个数的和相加等于偶数的话，那么其中一定有偶数个奇数。即0个或2个奇数
按照以上的思路很快可以确定，在内层的数字只有可能是1，3，5，7，9
然后
1不能和3处在同一三角形，7和9不能在同一三角形，1和9若在同一三角形时，3和7一定不在同一三角形
就这样可以推出结果。
10
8 1 5 2
7 9
3
6 4
下面来研究如何编程…………：）
既然是小学奥数，就应该用这种发法，牛！Top
96 楼ggyz（小虫）回复于 2006-06-01 14:18:37 得分 0
markTop
97 楼cmliang（才能）回复于 2006-06-01 15:03:31 得分 0
这是一个递归算法,看看pascal程序设计中的八皇后算法就知道了,出题的人是傻必,应该有多个解的.Top
98 楼heihei2004（嘿嘿）回复于 2006-06-01 15:15:41 得分 0
线性代数？Top
99 楼flyskytoday（夜漫漫路漫漫）回复于 2006-06-01 15:26:45 得分 0
NND
怎么读不明白啊
谁来解释一下Top
100 楼blnm2003（bl）回复于 2006-06-01 15:29:20 得分 0
learningTop
101 楼laomai（老迈）回复于 2006-06-01 17:01:41 得分 0
看看，呵呵Top
102 楼iwlk（http://www.ChinaFedora.cn/ fedora论坛）回复于 2006-06-01 17:05:53 得分 0
http://community.csdn.net/Expert/topic/4794/4794120.xml?temp=.6906855Top
103 楼beishion（）回复于 2006-06-01 17:12:36 得分 0
mark！Top
104 楼dong127（冬雪）回复于 2006-06-01 17:22:47 得分 0
markTop
105 楼chenvb（绝版部落）回复于 2006-06-01 17:54:03 得分 0
高Top
106 楼lauer0246（lauer）回复于 2006-06-01 18:03:55 得分 0
MARK先,实战更有效Top
107 楼cleansunshing（努力学习中）回复于 2006-06-01 18:34:31 得分 0
呵呵，笔算5分钟解决，结果楼上的已经给出了，编程先MARK下，明天来看Top
108 楼peilianhai（网侠（）回复于 2006-06-01 19:05:07 得分 0
出来结果再来看Top
109 楼darklight2008（其实我是水瓶座）回复于 2006-06-01 19:26:34 得分 0
mark............Top
110 楼phaetonbl（凳子）回复于 2006-06-01 22:15:24 得分 0
这道题袁锋兄给出的答案很精彩....
综合一下楼上兄弟的意见,我觉得此题也可以从下面这个思路解决:
(1)窮舉出來十組
1，5，10
1，6，9
1，7，8
2，4，10
2，5，9