参考 http://blog.csdn.net/wcyoot/article/details/6428305
1. 问题
给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:
【0,1,2,3,4,5,6,7,8,9】
举一个例子,
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次,1在下排出现了2次,
2在下排出现了1次,3在下排出现了0次....
以此类推..
2. 分析
关键是理解“要求下排每个数都是先前上排那十个数在下排出现的次数”。
做以下分析:设总共有n个数,上排a[0...n-1],下排b[0...n-1],。
1)下排n个数的累加和为n,即b[0]+b[1]+...+b[n-1] = n
2)ai*bi的累加和也为n,即a[0]*b[0]+a[1]*b[1]+...+a[n-1]*b[n-1] = n
3)对于b中任意一个元素b[j], 都存在i,a[i] = b[j].
还可以分析出更多的限制条件,这里就不继续了。
可参考http://blog.csdn.net/wcyoot/article/details/6428305
根据以上分析,可以看出其实这个题目的本质是一个多元一次不定方程。在未知数较少,分析出的限制条件越多的情况下,手算出结果是完全可能的。下面根据以上条件给出代码
3. 代码
思路:
依次将下排数组b的最后一个元素值设置为上排数组a的第i个元素值;
如果满足条件2), 则两个数组大小减1, 递归这个过程。
如果数组大小为0, 说明递归结束, 检查条件1)和2)是否满足, 若满足则打印出结果。
# -*- coding: utf-8 -*- # 求两个列表的乘积和 def list_sum(a, b): size = len(a) c = [a[i] * b[i] for i in range(0, size)] #print c return sum(c) # 检查a每个元素中每个元素在b中出现的次数是否满足要求 def check(a, b): for i in range(len(a)): if b.count(a[i]) != b[i]: return False return True # a 上排数组 # b 下排数组 # target 目标和(列表大小) # size 列表当前大小 def calc(a, b, target, size): if 0 == size: if sum(b) == target and list_sum(a, b) == target: #print b, check(a, b) if check(a, b): print a print b print '*' * 10 return for i in range(0, target): b[size - 1] = a[i] if b[size - 1] * a[size - 1] <= target: calc(a, b, target, size - 1) if __name__ == '__main__': ''' a = [0,1 , 2, 3, 4, 5, 6, 7, 8, 9] b = [0 for i in range(0, 10)] calc(a, b, 10, 10) ''' a = [0,1 , 2, 3, 4, 5, 6, 7] b = [0 for i in range(0, 8)] calc(a, b, 8, 8) ''' # 上排无0, 全0解 a = [1 , 2, 3, 4, 5, 6, 7, 8] b = [0 for i in range(0, 8)] calc(a, b, 8, 8) '''
运行结果如下
相关推荐
3--[scratch算法练习-水仙花数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-水仙花数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-水仙花数].zip...
算法专项练习---递推.ppt
4--[scratch算法练习-检测回文数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码4--[scratch算法练习-检测回文数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码4--[scratch算法练习-检测回...
3--[scratch算法练习-猜数字].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-猜数字].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-猜数字].zip源码...
算法专项练习--线型动态规划.ppt
2--[scratch算法练习-求平均年龄].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-求平均年龄].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-求平均年龄...
[Java算法练习]-获取指定位数.java
scratch2源码算法练习-水仙花数本资源系百度网盘分享地址
算法练习-水仙花数-少儿编程scratch项目源代码文件案例素材.zip
[Java算法练习]-十数排序.java
scratch2源码算法练习-检测回文数本资源系百度网盘分享地址
2--[scratch算法练习-在正方形内吗?].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-在正方形内吗?].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-在...
scratch2源码算法练习-猜数字本资源系百度网盘分享地址
2--[scratch算法练习-价格查询].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-价格查询].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-价格查询].zip...
4--[scratch算法练习-列表倒序].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码4--[scratch算法练习-列表倒序].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码4--[scratch算法练习-列表倒序]....
2--[scratch算法练习-打电话].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-打电话].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-打电话].zip源码...
2--[scratch算法练习-分段函数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-分段函数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-分段函数].zip...
2--[scratch算法练习-计算天数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-计算天数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[scratch算法练习-计算天数].zip...
3--[scratch算法练习-分配任务].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-分配任务].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-分配任务].zip...
3--[scratch算法练习-存款收益].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-存款收益].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码3--[scratch算法练习-存款收益].zip...