python分苹果问题_分苹果问题的C++和Python实现

很好玩的一个问题。话说小明的苹果怎么可能一模一样？

显然这并不是重点。重点在于抽象这个问题的方法。

如果从M个苹果，拿出N个苹果，问有几种可能性，很明显这是典型的组合问题；

如果把M个苹果等分成N份。显然只有1种可能。

把苹果分成N堆，求可能性，我一时半会想不出什么数学模型。自然而然，想到了数学方法：迭代逼近和递归。

题目额外说明，1，3，1 和1，1，3算同一种分法。其分发可能等价于将苹果递减或者递增排列。

于是我们开始递归计数：

递归操作：遍历M~0，如果存在M比数组之前的元素小，说明这是递减情况下的最大可能，就给新的元素赋值M，并且为剩下的元素进行递归操作。

递归退出条件： 数组最后一位也完成赋值(剩下的元素正好小于等于之前的数)。

递归退出操作： 计数器加一。如果愿意，可以输出此时的数组。

C++ 实现算法(值得我自己练习和细品)

#include “stdafx.h”

#include 

int Count = 0;

using namespace std;

void printArr(int dishNum, int* arr){

for (int i = 0; i 

for (int j = 0; j 

cout <

cout <

}

cout <

}

void allocation(int appleNumLeft, int dishNum, int idx, int* arr){

if (idx == (dishNum – 1)){

if (arr[idx – 1] >= appleNumLeft){

arr[idx] = appleNumLeft;

Count++;

printArr(dishNum, arr);

return;

}

else

return;

}

else{

for (int j = appleNumLeft; j >= 0; j–){

if (idx == 0){

arr[idx] = j;

allocation(appleNumLeft – j, dishNum, idx + 1, arr);

}

else{

if (arr[idx – 1] >= j){

arr[idx] = j;

allocation(appleNumLeft – j, dishNum, idx + 1, arr);

}

}

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int M, N;

cin >> M >> N;

int *a = new int[N];

allocation(M, N, 0, a);

cout <

delete[]a;

a = NULL;

return 0;

}

验证算法正确。

每递归一层，递归函数中的循环缩短一层。直到到达最后一遍。如果不存在最小值，则返回而不累加计数器。

然后是用python誊写算法。誊写过程中的关键点：

python没有引用的传递，取而代之的是全局列表。

for循环为迭代器。

全局列表需要初始化。

由于可以直接print列表，省去了一个print函数(所以没有打印苹果T_T)

没有用面向对象，感觉怪怪的。应该创建个苹果分配器类啥的。

#-*-coding:utf-8-*

def allocate(M,N,idx):

global a ,count

if idx==N-1:

if a[idx-1]>=M :

a[idx]=M

count+=1

print a

return

else:

return

else:

for i in reversed(range(0,M+1)):

if idx==0:

a[idx]=i

allocate(M-i,N,idx+1)

else:

if a[idx-1]>=i:

a[idx]=i

allocate(M-i,N,idx+1)

if __name__==’__main__’:

M,N=raw_input(“请输入苹果数和盘子数,并且用空格隔开\n”).strip().split()

a=[]

for i in range(0,int(N)):

a.append(0)

count=0

allocate(int(M),int(N),0)

print count

两段代码的视觉简洁度的区别非常明显。python天生具有好的可阅读性，而且编写便捷度也不赖(缩进比花括号好输入多了。),代码短了近一半，也许对于ROP不友好:p (ROP=Resume Oriented Programming)