数学高手编程高手进

Osullivan

1--9填入方格，数字不准重负，使等式成立
附件2为这题做的FLASH，可以下下来做这道题~~~~~~~~~~~~

matrixcl

/*
1 - 9 数字填入

□     □     □
---- + ---- + ---- = 1
□□   □□   □□


a0     a3     a6
---- + ---- + ---- = 1
a1a2   a4a5   a7a8

a0*a4a5*a7a8 + a3*a1a2*a7a8 + a6*a1a2*a4a5 = a1a2*a4a5*a7a8

*/
void FillNum(int * arr, int index)
{
        int i, j;
        for (i = 1; i <= 9; i++)
        {
                for (j=0; j<index; j++)
                {
                        if (arr[j] == i)
                                break;
                }
                if (j == index)
                {
                        arr[index] = i;
                        if (index < 8)
                        {
                                FillNum(arr, index+1);
                        }
                        else
                        {
                                if (arr[0] * (arr[4] * 10 + arr[5]) * (arr[7] * 10 + arr[8]) + arr[3] * (arr[1] * 10 + arr[2]) * (arr[7] * 10 + arr[8])
                                        + arr[6] * (arr[1] * 10 + arr[2]) * (arr[4] * 10 + arr[5]) == (arr[1] * 10 + arr[2]) * (arr[4] * 10 + arr[5]) * (arr[7] * 10 + arr[8]) )
                                {
                                        printf("-------------------------------n");
                                        printf(" %2d     %2d     %2dn", arr[0], arr[3], arr[6]);
                                        printf("---- + ---- + ---- = 1n");
                                        printf("%2d%2d   %2d%2d   %2d%2dn", arr[1], arr[2], arr[4], arr[5], arr[7], arr[8]);
                                }
                                return;
                        }
                }
        }
}
void main()
{
        int arrNum[9];
        FillNum(arrNum, 0);
}

C++写的，递归实现
排列组合的问题，用程序似乎效率都不高，一般都是穷举法

Osullivan

原帖由 oboe 于 2009-6-9 08:43 发表


补充一点，
要把三个分数由大到小排列起来，
第一个数是必大于1/3
改正一下：

要把三个分数由大到小排列起来，
前二个数之和必大于2/3

跟偶的想法一样哦~~~~~~~~
顶~~~~~

oboe

原帖由 oboe 于 2009-6-9 08:39 发表

当你选择的第一个分数是小于1/3，那么后面的排列组合可以不考虑穷举了。

同理，前二个分数之和必定要大于1/2

...

补充一点，
要把三个分数由大到小排列起来，
第一个数是必大于1/3
改正一下：

要把三个分数由大到小排列起来，
前二个数之和必大于2/3

[ 本帖最后由 oboe 于 2009-6-9 08:53 编辑 ]

oboe

原帖由 r_517 于 2009-6-2 22:36 发表


完全是无稽之谈。。。首先9/12=3/4，其次根据平均数原理只能证明至少有一个数大于1/3。完全无法得到其他任何结论。为什么9/12 “一定要存在”。就不可能是9/13、9/14……之类的么？

9/12是3/4。
之前我是计算错了一点。

但总体思路应该没错。
我的意思是：
三个分数相加等于1，那么必有一个分数大于1/3
所以，
当你选择的第一个分数是小于1/3，那么后面的排列组合可以不考虑穷举了。

同理，前二个分数之和必定要大于1/2

这样的算法，比递归的计算量要小一些。

77880066

还是有高手的啊啊

superacid

LS不愧是去年上海市NOIP第N名啊！
(注：我在 ★ 数学、算术趣题 ★ 里发帖的所有N都表示一个数)

铯_猪哥恐鸣

不用这样，直接用一个boolean数组表示某个数有没有用过，然后一部递归就行了。。你这样编程复杂度太大。。。9个数字还好，100个怎么办？（当然那样时间复杂度也超了，但如果有高效剪枝的话说不定还是可行的）

superacid

只要用8个变量a到h就可以了
i=45-a-b-c-d-e-f-g-h

visvate

         .