你和四个朋友一起去一家外国饭店吃饭。菜单上有9种菜，但是一个字都不认识，服务员说话也听不懂，要的菜也不知道谁要的是什么。唯一可以用来判别菜的是数量：如果你们要了三个 sdfdaskkj，两个 kljksdfsda，结果来了三个炸大虾，两个清蒸鱼，那 sdfdaskkj 就是炸大虾，kljksdfsda 就是清蒸鱼。假设你们每次要5个菜，你们去吃几顿饭才可以认清所有的菜？
如果一共m个人，去k次，最多可以认清几个菜？
原题野菜花已经给出正确答案。下面是推广题的答案。（很难看的答案。）
设最多可以认清的菜的数量为f(m,k)。对某一个菜，把每次要的数量放进一个k元数组：（2，0，3）表示第一次要了两个，第二次没要，第三次要了三个。如果两个菜的k元数组不一样，就能够区分开。这个问题于是变成找一个非负整数k元数组的集S，使得S中k元数组在每个坐标的和不大于m，并且使|S|最大。www.ddhw.com
为了让|S|大，每个k元数组中各坐标的和越小越好。对给定的i，各坐标的和等于i的k元数组共有C（k+i-1,i)个。这些k元数组在每个坐标的和等于C（k+i-1,i)*i/k = C(k+i-1,i-1)。把这两个数从1到i加起来，有
C(k,1)+C(k+1,2)+...+C(k+i-1,i) = C(k+i,i) - 1
C(k,0)+C(k+1,1)+...+C(k+i-1,i-1) = C(k+i,i-1)
即f(C(k+i,i-1),k) = C(k+i,i) - 1。k = 3, i = 2 时有 f(5,2) = 9，就是原来的题。
对不同的i之间的m值，f 基本上是线性的，即给定k之后，f(m,k)基本上是折线函数。更准确一点，设 m = C(k+i,i-1) + j，其中 i 是使 m >= C(k+i,i-1) 的最大值。则有
f(m,k) = C(k+i,i) - 1 + [j*k/(i+1)]。
例如10个人吃6顿饭，i=2, j=2。f(10,6) = C(8,2) - 1 + [2*6/3] = 31。即最多可以认清31个菜。
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-11-16 20:34:30
收藏
分享
支持
反对
置顶卡
千斤顶
发表于 2005-11-17 09:55:13
楼主