可用分押宝游戏火热进行中...	专题改版：Java Web 专题

面试归来，被一个小学的奥赛题放倒

楼主ongzi（）2006-05-28 14:26:38 在 Java / J2SE / 基础类提问

题目是这样的：先在纸上用一笔画出一个五角星，然后在五角星的5个角上和内部交叉点上分别画上圆圈。也就是一共10个圆圈。从1-10这10个数中不能重复的填入到这10个圈里，使得这个五角星上的五个三角形上的数字相加的值都等与16

先写出答案，然后编程实现。问题点数：20、回复次数：36Top

1 楼qq14923349（剑神）回复于 2006-05-28 14:48:21 得分 0

杀鸡冉用牛刀Top

2 楼flymoon99（遗忘代码）回复于 2006-05-28 17:23:39 得分 10

分析了下,这个问题可以归结为对一个等边5边形的处理.5个顶点分别填一个数.
规则1:5个顶点数总合等于25.也就是80-55=25(80是5个三角形总和,55是1到10的总和,相减是重复的部分,也就是等边5边形.
规则2:相邻2个顶点数之和要大于5小于16
规则3:任意3个顶点数之和要不等于16

这样问题就变得简单了.
不知道我这样分析对不对....
Top

3 楼ongzi（）回复于 2006-05-28 17:47:05 得分 0

有中茅塞顿开的感觉了，！！

规则2:相邻2个顶点数之和要大于5小于16
规则3:任意3个顶点数之和要不等于16
怎么说？Top

4 楼flymoon99（遗忘代码）回复于 2006-05-28 18:05:45 得分 0

规则2:相邻2个顶点数之和要大于5小于16

相邻小于5的话怎么加,三角形也不会是16,大于16同理;

规则3:任意3个顶点数之和要不等于16

等于16的话,那用来构成和为16的三角形其中的3个点都在等边5变形顶点.5角星顶点就没有点可以表示数了,因为每个顶点都不一样
○
/ \
○-○----○-○
\ \ /
○ ○
/ \ / \
/ ○ \
○- ○

大概就这么表示下吧

Top

5 楼flymoon99（遗忘代码）回复于 2006-05-28 18:07:49 得分 0

另外还得加一条规则过滤下;
某个顶点数的2倍+另外一个顶点数 != 16Top

6 楼flymoon99（遗忘代码）回复于 2006-05-28 18:10:28 得分 0

喔,对了,还有相邻2个顶点数之和与另外任意2个相邻顶点数之和不能相等.(其实要注意的是等边5边形是循环的)Top

7 楼flymoon999（）回复于 2006-05-28 18:24:53 得分 5

郁闷,一个ID连续只能发3次.为了发布答案,只得重新申请个号了.如果给分的话,请给我原来的号吧^&^

答案只有一个
2
10 5 9 4
1 3
7
8 6

呵呵,只用C写了下,JAVA还没开始学Top

8 楼javatalk（）回复于 2006-05-28 22:29:39 得分 5

答案不只一个！
你的外顶点是2,10,8,6,4!
我的外顶点是1,7,6,10,5!
10
5 2 4 9
9 3
6
1 7

呵呵，不太一样吧！Top

9 楼javatalk（）回复于 2006-05-28 23:29:44 得分 0

呵呵，原来自己搞错了！Top

10 楼wjj0532（西农小小生）回复于 2006-05-28 23:56:51 得分 0

标记一下！Top

11 楼schol（敲击思想的键盘，滑动灵感的鼠标~~~好男儿志在四方）回复于 2006-05-29 07:56:37 得分 0

...脑袋晕了~~Top

12 楼schol（敲击思想的键盘，滑动灵感的鼠标~~~好男儿志在四方）回复于 2006-05-29 08:08:52 得分 0

什么公司出这种题，..变态！！Top

13 楼chizhaowei（阿冰）回复于 2006-05-29 08:43:31 得分 0

还有一个答案哦！

5
/ \
2----10-----1-----8
\ / \ /
4 7
/ \ / \
/ 3 \
/ / \ \
/ / \ \
/ / \ |
9 6Top

14 楼zbs_capricorn（）回复于 2006-05-29 10:46:40 得分 0

关注中....各位大哥可否把实现代码传上来参考一下Top

15 楼zhu_zhutian80（）回复于 2006-05-29 11:10:01 得分 0

厉害呀，flymoon99Top

16 楼flymoon99（遗忘代码）回复于 2006-05-29 11:12:03 得分 0

答案不只一个！
你的外顶点是2,10,8,6,4!
我的外顶点是1,7,6,10,5!
10
5 2 4 9
9 3
6
1 7

呵呵，不太一样吧！

你这里有2个9...
错了,呵呵Top

17 楼flymoon99（遗忘代码）回复于 2006-05-29 11:17:08 得分 0

chizhaowei(阿冰) ( ) 信誉：100 2006-05-29 08:43:00 得分: 0

还有一个答案哦！

5
/ \
2----10-----1-----8
\ / \ /
4 7
/ \ / \
/ 3 \
/ / \ \
/ / \ \
/ / \ |
9 6

这个确实是喔,可能我编程时条件判断没处理好^_^Top

18 楼wdt821229（eye ）回复于 2006-05-30 10:38:19 得分 0

怎么没有代码？Top

19 楼dukcho（天海空阔）回复于 2006-05-30 11:03:49 得分 0

数学建模的还是很有用的！Top

20 楼wangx1949（）回复于 2006-05-30 13:59:00 得分 0

mark.
期待代码及构建思路Top

21 楼woaiwanghuan（我不学习是猪）回复于 2006-05-30 14:02:30 得分 0

这个问题用回溯法解决!
不断的用数进行试探,不行就回溯,但在试探的时候,可以选择策略,减少试探的次数!Top

22 楼naga22（）回复于 2006-05-30 14:30:38 得分 0

牛！！！Top

23 楼BCMshuijing（水晶@_@）回复于 2006-05-30 15:03:04 得分 0

挺有意思，但水平有限，写的比较乱。
public class a {
public static void main(String[] args) {
int y=1,y5,y6,y7,y8,y9,y10;
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
if (j==i)
continue;
for(int k=0;k<10;k++)
{
if(k==i||k==j)
continue;
for(int l=0;l<10;l++)
{
if (l==k||l==j||l==i)
continue;
y5=25-i-j-k-l;
y6=16-i-y5;
y7=16-i-j;
y8=16-j-k;
y9=16-k-l;
y10=16-l-y5;
if (y5>10|y6>10|y7>10|y8>10|y9>10|y10>10)
continue;
if (y5<0|y6<0|y7<0|y8<0|y9<0|y10<0)
continue;
if (y5==i|y5==j|y5==k|y5==l|y5==y6|y5==y7|y5==y8|y5==y9|y5==y10)
continue;
if (y6==i|y6==j|y6==k|y6==l|y6==y7|y6==y8|y6==y9|y6==y10)
continue;
if (y7==i|y7==j|y7==k|y7==l|y7==y8|y7==y9|y7==y10)
continue;
if (y8==i|y8==j|y8==k|y8==l|y8==y9|y8==y10)
continue;
if (y9==i|y9==j|y9==k|y9==l|y9==y10)
continue;
if (y10==i|y10==j|y10==k|y10==l)
continue;
else
System.out.println("第"+y+++"个符合条件的： "+i+" "
+j+" "+k+" "+l+" "+y5+" "
+y6+" "+y7+" "+y8+" "+y9
+" "+y10);
}
}
}
}
}
}Top

24 楼BCMshuijing（水晶@_@）回复于 2006-05-30 15:05:11 得分 0

第1个符合条件的： 1 5 9 3 7 8 10 2 4 6
第2个符合条件的： 1 7 3 4 10 5 8 6 9 2
第3个符合条件的： 1 7 3 9 5 10 8 6 4 2
第4个符合条件的： 3 7 1 5 9 4 6 8 10 2
第5个符合条件的： 3 9 5 1 7 6 4 2 10 8
第6个符合条件的： 4 3 7 1 10 2 9 6 8 5
第7个符合条件的： 5 1 7 3 9 2 10 8 6 4
第8个符合条件的： 5 9 3 7 1 10 2 4 6 8
第9个符合条件的： 7 1 5 9 3 6 8 10 2 4
第10个符合条件的： 7 3 9 5 1 8 6 4 2 10
第11个符合条件的： 9 3 7 1 5 2 4 6 8 10
第12个符合条件的： 9 5 1 7 3 4 2 10 8 6Top

25 楼BCMshuijing（水晶@_@）回复于 2006-05-30 15:10:14 得分 0

结果的顺序是这样的：
6
/ \
10----5-----1-----7
\ / \ /
4 2
/ \ / \
/ 3 \
/ / \ \
/ / \ \
/ / \ |
9 8
Top

26 楼UnAgain（）回复于 2006-05-30 15:33:45 得分 0

flymoon99(遗忘代码)分析得很好Top

27 楼BCMshuijing（水晶@_@）回复于 2006-05-30 16:49:00 得分 0

先确定内部交叉点儿上五个数字中的四个，然后其它的六个数字就可以算出来了，然后再判断这十个数字是不是符合题中的条件，所以，用四个循环，一个一个的试探就行了。
出来的结果有12个，但好多一样的，逆时针和顺时针填算一个的话，答案就两个：
8
/ \
6----7-----1-----10
\ / \ /
3 5
/ \ / \
/ 9 \
/ / \ \
/ / \ \
/ / \ |
4 2

5
/ \
2----10-----1-----8
\ / \ /
4 7
/ \ / \
/ 3 \
/ / \ \
/ / \ \
/ / \ |
9 6Top

28 楼chen_2001（刀锋）回复于 2006-05-30 17:11:42 得分 0

我的答案：
2

4 9 5 10
3 1
7
6 8

Top

29 楼zbs_capricorn（）回复于 2006-05-31 21:39:48 得分 0

这是个很好的问题啊，怎么没有解决完就沉底了呢！Top

30 楼javabeginner2006（）回复于 2006-05-31 22:16:44 得分 0

其实这种面试题不在考你会不会,而是考你的思路清晰不清晰,其实到flymoon99(遗忘代码)那基本已经可以把答案做出来了.Top

31 楼sun0201（）回复于 2006-06-01 00:56:51 得分 0

关注Top

32 楼ackeer（）回复于 2006-07-12 08:16:12 得分 0

是个不错的东东

看完答案，排便都通常多了Top

33 楼mydo（侯佩|hopy|ks）回复于 2006-07-12 08:27:29 得分 0

我的解决方案:

;* * * * * * * * * * *
;5 STAR POWER VER * *
;* * * * * * * * * * *

.386
.model flat,stdcall
option casemap:none

include c:\masm32\include\windows.inc
include c:\masm32\include\user32.inc
includelib c:\masm32\lib\user32.lib
include c:\masm32\include\kernel32.inc
includelib c:\masm32\lib\kernel32.lib

.const
dllname db 'msvcrt.dll',0
fucmalloc db 'malloc',0
fucfree db 'free',0
ft db 'Total Time: %d (ms) Total Times == %d Finded == %d',0
fft db '%s',0
cp db 'windows xp (sp2)',0
cpc db '5 Star Power Ver',0
szClass db 'Notepad',0
szexit db 'Press Any Key To Exit...',0
ten dd 10

.data?
hInstance dd ?
nbn dw ? ;Numbers Bit Now
dw ?
TTs dd ?
FC dd ? ;Finded Counter
tmptime dd ?
hpad dd ?
hstdout dd ?
hstdin dd ?
lpnum dd ?
ncn db 10 dup (?) ;Number Combination Now unZip
fbuf db 512 dup (?)
buf db 512 dup (?)

.code
;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
ShowLastC proc
local i

xor eax,eax
mov i,0
.while TRUE
mov al,[edi]
.break .if al == 0
.if al == 10
mov al,65
.else
add al,30h
.endif
mov buf[0],al
invoke WriteConsole,hstdout,addr buf,1,addr lpnum,NULL
mov byte ptr buf[0],' '
invoke WriteConsole,hstdout,addr buf,1,addr lpnum,NULL
inc i
xor edx,edx
mov eax,i
div ten
.if edx == 0
mov byte ptr buf[0],0ah
invoke WriteConsole,hstdout,addr buf,1,\
addr lpnum,NULL
.endif
inc edi
.endw
invoke WriteConsole,hstdout,addr buf,1,\
addr lpnum,NULL
invoke WriteConsole,hstdout,addr szexit,sizeof szexit,\
addr lpnum,NULL
invoke ReadConsole,hstdin,addr buf,1,lpnum,NULL

ret
ShowLastC endp

;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
ShowLastW proc
local i

invoke FindWindow,addr szClass,NULL
.if eax
mov ecx,eax
invoke ChildWindowFromPoint,ecx,20,20
.endif
.if eax
mov hpad,eax
lea edi,fbuf
xor eax,eax
mov i,0
.while TRUE
mov al,[edi]
.break .if al==0
.if al==10
mov al,65
.else
add al,30h
.endif
invoke PostMessage,hpad,WM_CHAR,eax,1
mov al,' '
invoke PostMessage,hpad,WM_CHAR,eax,1
inc i
xor edx,edx
mov eax,i
div ten
.if edx == 0
mov al,0dh
invoke PostMessage,hpad,WM_CHAR,eax,1
.endif

inc edi

.endw
.else
jmp quitme
.endif

quitme:
ret

ShowLastW endp
;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
calcncn proc

mov al,ncn[0]
add al,ncn[1]
add al,ncn[2]
sub al,16
jnz quitme
mov al,ncn[2]
add al,ncn[3]
add al,ncn[4]
sub al,16
jnz quitme
mov al,ncn[4]
add al,ncn[5]
add al,ncn[6]
sub al,16
jnz quitme
mov al,ncn[6]
add al,ncn[7]
add al,ncn[8]
sub al,16
jnz quitme
mov al,ncn[8]
add al,ncn[9]
add al,ncn[0]
sub al,16
jnz quitme

lea edi,fbuf
mov ebx,FC
lea ebx,[ebx*8]
add ebx,FC
add ebx,FC
mov eax,dword ptr ncn[0]
mov dword ptr [edi+ebx],eax
mov eax,dword ptr ncn[4]
mov dword ptr [edi+ebx+4],eax
mov ax,word ptr ncn[8]
mov word ptr [edi+ebx+8],ax

inc FC
quitme:
ret

calcncn endp
;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
calcncn2 proc

mov al,ncn[0]
add al,ncn[1]
add al,ncn[2]
.if al != 16
jmp quitme
.endif
mov al,ncn[2]
add al,ncn[3]
add al,ncn[4]
.if al != 16
jmp quitme
.endif
mov al,ncn[4]
add al,ncn[5]
add al,ncn[6]
.if al != 16
jmp quitme
.endif
mov al,ncn[6]
add al,ncn[7]
add al,ncn[8]
.if al != 16
jmp quitme
.endif
mov al,ncn[8]
add al,ncn[9]
add al,ncn[0]
.if al != 16
jmp quitme
.endif

lea edi,fbuf
mov ebx,FC
lea ebx,[ebx*8]
add ebx,FC
add ebx,FC
mov eax,dword ptr ncn[0]
mov dword ptr [edi+ebx],eax
mov eax,dword ptr ncn[4]
mov dword ptr [edi+ebx+4],eax
mov ax,word ptr ncn[8]
mov word ptr [edi+ebx+8],ax

inc FC
quitme:
ret

calcncn2 endp
;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
;Inc ncn ,Return 1 == OK,0 == err,-1 == overflow:means all over ^0^
incncn proc
local tmpRT
local i
;align 4

;push eax
;push ecx
;push ebx

mov tmpRT,0
xor ecx,ecx
xor eax,eax
xor ebx,ebx
.while ecx<10 ;ecx<10

mov al,ncn[ecx]
t0:
inc al
.if al>10 ;al>10
inc ecx
.continue
.else
push ecx
inc ecx
mov nbn,0
.while ecx<10 ;ecx<10
mov bl,ncn[ecx]
.if bl == al
pop ecx
jmp t0
.else
bts nbn,bx
inc ecx
.endif
.endw
pop ecx
mov ncn[ecx],al
bts nbn,ax
dec ecx
.while ecx != 0ffffffffh
mov ax,1
.while ax<=10 ;ax<=10
bt nbn,ax
.if CARRY?
inc ax
.continue
.else
mov ncn[ecx],al
bts nbn,ax
.break
.endif
.endw
dec ecx
.endw
mov tmpRT,1
jmp quitme
.endif

.endw
mov tmpRT,-1
quitme:
;pop ebx
;pop ecx
;pop eax
mov eax,tmpRT
ret

incncn endp

;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
;Init ncn
initncn proc

push eax
mov eax,01020304h
mov dword ptr ncn[6],eax
mov eax,05060708h
mov dword ptr ncn[2],eax
mov ax,090ah
mov word ptr ncn[0],ax
pop eax
ret

initncn endp
;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
start:
invoke GetModuleHandle,NULL
mov hInstance,eax
invoke SetConsoleTitleA,addr cpc
invoke GetStdHandle,STD_INPUT_HANDLE
mov hstdin,eax
invoke GetStdHandle,STD_OUTPUT_HANDLE
mov hstdout,eax
invoke initncn
mov FC,0
mov TTs,1
invoke GetTickCount
mov tmptime,eax
.repeat
invoke calcncn
invoke incncn
inc TTs
.until eax == -1
dec TTs
invoke GetTickCount
sub eax,tmptime

invoke wsprintf,addr buf,addr ft,eax,TTs,FC
invoke MessageBox,NULL,addr buf,addr cp,MB_OK

;invoke ShowLastW
invoke ShowLastC

invoke CloseHandle,hstdin
invoke CloseHandle,hstdout
invoke ExitProcess,NULL
;~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
end startTop

34 楼mydo（侯佩|hopy|ks）回复于 2006-07-12 08:30:09 得分 0

解释如下:

a 大家不要看代码长，其实我在计算匹配和显示输出时都分别写了两种算法。
显示一个是 console 显示，一个是 gui32 显示。

b 控制台显示结果如下:

A 5 1 8 7 6 3 9 4 2
9 4 3 6 7 8 1 A 5 2
5 A 1 8 7 6 3 4 9 2
4 9 3 6 7 8 1 5 A 2
9 2 5 A 1 8 7 6 3 4
3 6 7 8 1 A 5 2 9 4
A 2 4 9 3 6 7 8 1 5
1 8 7 6 3 9 4 2 A 5
7 8 1 A 5 2 9 4 3 6
7 8 1 5 A 2 4 9 3 6
3 9 4 2 A 5 1 8 7 6
3 4 9 2 5 A 1 8 7 6
7 6 3 9 4 2 A 5 1 8
7 6 3 4 9 2 5 A 1 8
1 A 5 2 9 4 3 6 7 8
1 5 A 2 4 9 3 6 7 8
4 2 A 5 1 8 7 6 3 9
3 6 7 8 1 5 A 2 4 9
5 2 9 4 3 6 7 8 1 A
1 8 7 6 3 4 9 2 5 A

Press Any Key To Exit...Top

35 楼mydo（侯佩|hopy|ks）回复于 2006-07-12 08:31:42 得分 0

A 代表 10

计算总耗时 : 1938(ms) ,共枚举 3628800 次，共找到 20 个符合条件的组合。Top

36 楼yitianyidian（至之）回复于 2006-07-12 11:11:04 得分 0

厉害Top