p*****i
发帖数: 197 | 1 You have 40 cans, all placed in a line at exact intervals of one meter.
You also have 9 apples. You wish to place all the apples in the cans, no
more than one apple in each can, so that there are no three apples A, B,
and C such that the distance between A and B is equal to the distance
between B and C. How many ways can you arrange the apples in the cans?
怎么解？ | t**r
发帖数: 3428 | | p*****i
发帖数: 197 | 3 ？
【在 t**r 的大作中提到】
: mark
| b******u
发帖数: 81 | 4 7555794
1, 2, 6, 7, 9, 14, 15, 18, 20
bruite force or
public static int GetCount2(int numOfApples, int numOfLocations)
{
List set = new List();
for (int i = 1; i <= numOfApples; i++ )
{
set = GetSetForAddingOneMoreAppleAtTheEnd(set,
numOfLocations - numOfApples + i);
}
return set.Count;
}
public static List GetSetForAddingOneMoreAppleAtTheEnd(List<
int[]> existingSet, int numOfLocations )
{
List result = new List();
if (existingSet.Count == 0)
{
for (int i = 1; i <= numOfLocations; i++)
{
int[] loc = { i };
result.Add(loc);
}
return result;
}
foreach (int[] locations in existingSet)
{
int max = locations.Max(i => i);
int cnt = locations.Length;
for (int i = max + 1; i <= numOfLocations; i++)
{
if (IsTheNewAppleOk(locations, cnt, i))
{
int[] newLocations = new int[cnt + 1];
for (int j = 0; j < cnt; j++)
{
newLocations[j] = locations[j];
}
newLocations[cnt] = i;
result.Add(newLocations);
}
}
}
return result;
}
public static bool IsTheNewAppleOk(int[] applPos, int cnt, int
newPos)
{
if (cnt <= 1) return true;
for (int i = 0; i < cnt; i++)
{
for (int j = i + 1; j < cnt; j++)
{
if (applPos[i] + newPos == 2 * applPos[j])
{
return false;
}
}
}
return true;
} | p*****2
发帖数: 21240 | 5 recursion。
至少需要37个苹果。第一个苹果可以放在1－4的位置上。下一个苹果可以放到下1到10
的位置上。
然后要剪枝。苹果之间的间隔可以是1－10,用hashtable放已经用过的间隔。通过统计
还可以剪掉8－10已经不能用的。 | c*****l
发帖数: 20 | 6 bajiezhu 提供的解答 (#4)
IsTheNewAppleOk（） 的 time complexity 是 O(n^2)
用下面的方法可以更快一些
使用一个数组 postion[1..40],初始值设为0,
如果 apple i 可以放在 position[j], position[j] == i
如果position j 因为已放进罐子里的 apples 的限制, 不可使用，position[j] 将设
为负数（请看下面的算法）
搜寻下一个 j, and position[j] == 0
那么 apple i 可以放在 position[j], position[j] = i;
计算所有已经放进罐子 apple[1..i-1] 的距离
如果 apple k 和 apple i 的距离是 d
position[j+d] -= k | C***U
发帖数: 2406 | 7 dp?
【在 p*****i 的大作中提到】
: You have 40 cans, all placed in a line at exact intervals of one meter.
: You also have 9 apples. You wish to place all the apples in the cans, no
: more than one apple in each can, so that there are no three apples A, B,
: and C such that the distance between A and B is equal to the distance
: between B and C. How many ways can you arrange the apples in the cans?
: 怎么解？
| C***U
发帖数: 2406 | 8 brute force的算法我写过 大概3秒中能算出来
【在 p*****i 的大作中提到】
: You have 40 cans, all placed in a line at exact intervals of one meter.
: You also have 9 apples. You wish to place all the apples in the cans, no
: more than one apple in each can, so that there are no three apples A, B,
: and C such that the distance between A and B is equal to the distance
: between B and C. How many ways can you arrange the apples in the cans?
: 怎么解？
|
|
