【转】24位老人分三桌就餐有关问题（200分）

【转】24位老人分三桌就餐问题（200分）
退休那年，看到赵慈庚在 <数学通报> 提出一个未曾解决的问题：有24位老人，从76岁到99岁，每岁一人，他们分三桌就餐，每桌8人，要求各桌年龄的和相等，问有多少种分桌法？

当时我考虑过，试图解决，可是两次都失败了。后来再未考虑。今翻看旧日笔记，又想碰碰它，仍未能解决，现在提出来，希望大家来帮助。

【注】这个问题应属于算法问题，但现在在《专题开发》板块中已找不到《算法和数据结构》小块了，所以我只得将问题放在这里，因为原来《算法和数据结构》是和《图形图像》合在一起的，或许很多老手还忘不了这里...

------解决方案--------------------
分成12对，保证每对的年龄都等于平均年龄乘以2，即：(76,99)(77,98)(78,97)(79,96)，只要保证每一对在同一桌，就可以达到题目要求，也就成了一个排列组合。
但这只是得到一部分解
------解决方案--------------------
找出8个和为700的组合，剩余的16个里面找出8个和为700的组合

然后总的除以3

未解决不至于吧，最多效率慢点。
------解决方案--------------------

#include <iostream>

#include <ctime>

using namespace std;


const int MaxN = 24;

const int MaxM = 3;

int assign[MaxN], cursum[MaxM], curcount[MaxM], target;

int result;

void DFS(int i, int maxassigned)

{

	if(i < 0)

	{

		++result;

		return;

	}

	for(int j=0;j<=maxassigned+1 && j < MaxM;j++)

	{

		if(cursum[j] + i > target)

			continue;

		if(curcount[j] + 1 > MaxN / MaxM)

			continue;

		assign[i] = j;

		cursum[j] += i;

		++curcount[j];

		DFS(i-1, j>maxassigned ? j : maxassigned);

		cursum[j] -= i;

		--curcount[j];

	}

}

int main()

{

	target = MaxN * (MaxN-1) / 2 / MaxM;

	DFS(MaxN-1, -1);

	cout<<"Result: "<<result<<endl;

	cout<<"Elapsed time "<<(double)clock()/CLOCKS_PER_SEC<<endl;

	return 0;

}

Result: 1025113
Elapsed time 0.218

几分钟迅速写了一个小程序。
------解决方案--------------------
看你怎么定义同类问题了。大框架搜索类型的题碰到过很多。具体有没有和这道题类似的话那就不记得了。
------解决方案--------------------
才24个人，还有这么多限制，暴力绝对能搞。
------解决方案--------------------
楼主要的是数学公式。
可惜，组合数学的公式往往比较复杂，况且这里也不方便对公式排版。
------解决方案--------------------
5#能讲讲思路么
------解决方案--------------------
既然写了还是贴出来吧，就当备份代码了。

using System;


public class Test

{

    static int[] Counter = new int[3];

    static int[] Sum = new int[3];

    static int Result = 0;

    static int CountValue = 8, SumValue = 100;


    static void Dfs(int num, int max)

    {

        if (num == 0)

            Result++;

        else

        {

            for (int i = 0; i <= max; i++)

            {

                if (Counter[i] >= CountValue 
------解决方案--------------------
 Sum[i] + num > SumValue)

                    continue;


                if (Counter[i] + 1 == CountValue && Sum[i] + num != SumValue)

                    continue;


                int maxNext = max < 2 && max == i ? i + 1 : max;

                Counter[i]++; Sum[i] += num;

                Dfs(num - 1, maxNext);

                Sum[i] -= num; Counter[i]--;

            }

        }

    }


    static void Main()

    {

        DateTime begin = DateTime.Now;

        Dfs(24, 0);

        Console.WriteLine(Result);

        Console.WriteLine(DateTime.Now - begin);

    }

}

------解决方案--------------------

引用:

Quote: 引用:

找出8个和为700的组合，剩余的16个里面找出8个和为700的组合

然后总的除以3

未解决不至于吧，最多效率慢点。