最近天作者：主题：内容：

您当前的位置：推理之门 > 谜题解析 > 谜题大全

【版主】：tl,艾米,popodian

字体大小：

第1页/共1页（总计5个回复）

主题： 15女生散步问题答案（人气：877）

gooeey（谷衣）

1 楼： 15女生散步问题答案

02年07月21日19点32分

题目：
15个女生出去散步，每3个人一组。她们每天出去散步一次
问：如何安排，在7天之内，可以使每个女生和其他14个女生出去散步一次

答案：下边是答案中的一种：（假定15个人的编号为：0~14）
第一天 0, 1, 2/ 3, 4, 5/ 6, 7, 8/ 9,10,11/12,13,14/
第二天 0, 3, 6/ 1, 8,14/ 2, 9,12/ 4, 7,10/ 5,11,13/
第三天 0,10,14/ 1, 3,11/ 7, 9,13/ 2, 4, 6/ 5, 8,12/
第四天 0, 7,11/ 5, 6,14/ 4, 8, 9/ 1,10,12/ 2, 3,13/
第五天 0, 8,13/ 3, 7,12/ 1, 6, 9/ 2, 5,10/ 4,11,14/
第六天 0, 4,12/ 1, 5, 7/ 2, 8,11/ 3, 9,14/ 6,10,13/
第七天 0, 5, 9/ 1, 4,13/ 2, 7,14/ 3, 8,10/ 6,11,12/

其中每个人和其他人出去的顺序为：

0 -- 1,2,3,6,10,14,7,11,8,13,4,12,5,9
1 -- 0,2,8,14,3,11,10,12,6,9,5,7,4,13
2 -- 0,1,9,12,4,6,3,13,5,10,8,11,7,14
3 -- 4,5,0,6,1,11,2,13,7,12,9,14,8,10
4 -- 3,5,7,10,2,6,8,9,11,14,0,12,1,13
5 -- 3,4,11,13,8,12,6,14,2,10,1,7,0,9
6 -- 7,8,0,3,2,4,5,14,1,9,10,13,11,12
7 -- 6,8,4,10,9,13,0,11,3,12,1,5,2,14
8 -- 6,7,1,14,5,12,4,9,0,13,2,11,3,10
9 -- 10,11,2,12,7,13,4,8,1,6,3,14,0,5
10 -- 9,11,4,7,0,14,1,12,2,5,6,13,3,8
11 -- 9,10,5,13,1,3,0,7,4,14,2,8,6,12
12 -- 13,14,2,9,5,8,1,10,3,7,0,4,6,11
13 -- 12,14,5,11,7,9,2,3,0,8,6,10,1,4
14 -- 12,13,1,8,0,10,5,6,4,11,3,9,2,7

本人通过编程的方法完成，编程序（包括设计算法，调试）用了4个小时
计算机运行30秒种得出答案
经过统计，假定设定一个值为一步，一共用了5344590步

　　点击复制本贴地址：

鬼谷子第四十六代传人
前知五百年后知五百年
有什么疑案？？
待我掐指算来。。。
嗯。。。原来如此。。。
这才是真相。。。。。。

※来源: 【推理之门 Tuili.Com 】.

holmos（大力）

2 楼： Re:15女生散步问题答案

02年07月19日16点02分

把算法简要贴出来一下吧，我个人挺感兴趣。:)

没有完美的犯罪......

※来源: 【推理之门 Tuili.Com 】.

gooeey（谷衣）

3 楼： Re:Re:15女生散步问题答案

02年07月19日16点35分

算法用到递归
a[7][5][3] 用于存储最后结果
b[15][15] 用于表示 b[j] 中的i 与 j是否一起出去过
c[7][15] 用于记录第 c[j] 中的第i天，第j号人有没有出去过
nI, nJ, nK 用于记录当前算的是第几天，第几组，第几个人的安排

main()
{
int i=0;
int j=0;
int k=0;

for (i=0; i＜7; i++)
for (j=0; j＜5; j++)
for (k=0; k＜3; k++)
a[j][k] = -1;
for (i=0; i＜15; i++)
for (j=0; j＜15; j++)
{
if (i==j)
b[j]=TRUE;
else
b[j]=FALSE;
}
nI=nJ=nK=0;
nBefore=0;
for (i=0;i＜7;i++)
for (j=0; j＜15; j++)
c[j]=FALSE;
nCount = 0;

Start();
}

void CMy357Dlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting

SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;

// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
}
}

void Start()
{
BOOL bTrue = TRUE;
while(bTrue)
{
bTrue = DoNext(nBefore);
}

}

void SetValue(int n)
{
nCount ++;

if (nCount == 2443)
{
int nTest = 0;
}
else if (nCount == 2460)
{
int nTest2 = 0;
}

a[nI][nJ][nK] = n;
if (nK == 2)
{
b[a[nI][nJ][0]][n] = TRUE;
b[a[nI][nJ][1]][n] = TRUE;
b[n][a[nI][nJ][0]] = TRUE;
b[n][a[nI][nJ][1]] = TRUE;
}
else if (nK==1)
{
b[a[nI][nJ][0]][n] = TRUE;
b[n][a[nI][nJ][0]] = TRUE;
}
}

int CMy357Dlg::DelValue()
{
int n=a[nI][nJ][nK];
if (2==nK)
{
b[a[nI][nJ][0]][n] = FALSE;
b[a[nI][nJ][1]][n] = FALSE;
b[n][a[nI][nJ][0]] = FALSE;
b[n][a[nI][nJ][1]] = FALSE;
}
else if (nK==1)
{
b[a[nI][nJ][0]][n] = FALSE;
b[n][a[nI][nJ][0]] = FALSE;
}
a[nI][nJ][nK] = -1;
c[nI][n] = FALSE;
return n;
}

BOOL DoNext(int n)
{
if (SetThis(n))
{
if (6==nI && 4==nJ && 2==nK)
{
//**输出答案**//
return FALSE;
}
else
{
nBefore=a[nI][nJ][nK];
nK++;
if (3 == nK)
{
nK = 0;
nBefore=0;
nJ ++;
if (5 == nJ)
{
nJ = 0 ;
nBefore=0;
nI ++;
}
}
return TRUE;//DoNext(n);
}
}
else
DelBefore();
}

void DelBefore()
{
nK--;
if (nK ＜ 0)
{
nK=2;
nJ--;
if (nJ＜0)
{
nJ=4;
nI--;
}
}
if (nI==0)
{
AfxMessageBox("No Result");
return;

}
int n = DelValue();
if (nJ == 0 && nK == 0)
{
DelBefore();
}
else
{
DoNext(n+1);
}
}

BOOL SetThis(int n)
{
BOOL bReturn = FALSE;
for (int i=n; i＜15; i++)
{
if (c[nI] == FALSE)
{
if ( 2== nK &&
b[a[nI][nJ][0]] == FALSE &&
b[a[nI][nJ][1]] == FALSE)
{
SetValue(i);
bReturn = TRUE;
c[nI] = TRUE;
break;
}
else if (1 == nK && b[a[nI][nJ][0]] == FALSE)
{
SetValue(i);
bReturn = TRUE;
c[nI] = TRUE;
break;
}
else if ( 0 == nK)
{
SetValue(i);
bReturn = TRUE;
c[nI] = TRUE;
break;
}
}

}
if (!bReturn)
DelBefore();
return bReturn;
}