[编程题]集合遍历
有K种颜色的小球(K<=10)，每种小球有若干个，总数小于100个。
现在有一个小盒子，能放N个小球(N<=8)，现在要从这些小球里挑出N个小球，放满盒子。
想知道有哪些挑选方式。注：每种颜色的小球之间没有差别。
请按数字递增顺序输出挑选小球的所有方式。
如有3种颜色，每种颜色小球的个数分别为a:1,b:2,c:3，挑出3个小球的挑法有：
003,012,021,102,111,120
输入描述:
第一行两个数字K N，分别表示小球种类数目和挑选的小球个数
第二行开始为每种小球的数目，共K行数据
输出描述:
输出所有可行的挑选方案，按升序排列
输入例子1:
3 3
1
2
3
输出例子1:
003
012
021
102
111
120
解法1：（c++）
| #include <iostream>
#include<vector>
#include<numeric>
using namespace std;
struct node{
int num;
vector<vector<int> > v;
};
int main(){
int K, N,Ki;
cin >> K >> N;
vector<node> ball(K);
for(int i=0;i<K;i++){
node p;
cin>>Ki;
ball[i].num=Ki;
}
if(K==1) cout<<N<<endl;
else {
vector<int> tmpv;
for(int i=0;i<=ball[0].num;i++) {
tmpv.push_back(i);
ball[0].v.push_back(tmpv);
tmpv.clear();
}
for(int i=1;i<K;i++){
for(int j=0;j<ball[i-1].v.size();j++){
for(int k=0;k<=ball[i].num;k++){
tmpv=ball[i-1].v[j];
tmpv.push_back(k);
if(i==K-1){
if(accumulate(tmpv.begin(),tmpv.end(),0)==N){
for(int l=0;l<tmpv.size();l++) cout<<tmpv[l];
cout<<endl;
}
}
else {
if(accumulate(tmpv.begin(),tmpv.end(),0)<=N) ball[i].v.push_back(tmpv);
}
tmpv.clear();
}
}
}
}
}
解法二（python）：
| import sys
K, N = list(map(int, sys.stdin.readline().split()))
def backtrace(i, my_dic, cnt, res, s):
if i == K and cnt == N:
res.append(''.join(s))
elif i < K:
for use in range(my_dic[i]+1):
if use <= N - cnt:
s.append(str(use))
backtrace(i+1, my_dic, cnt+use, res, s)
s.pop()
else:
break
if __name__ == '__main__':
my_dic = {}
for i in range(K):
my_dic[i] = int(sys.stdin.readline().strip())
res = []
backtrace(0, my_dic, 0, res, [])
for r in res:
print(r)
|
解法三（python）： # coding=utf-8
import sys
a = [0]*11
ans = [0]*11
k,n=0,0
def Print(k, ans):
res = ''
for i in range(k):
res += str(ans[i])
print(res)
def fun(i, n): # i可以认为是球类比的编号，ans[i]就是结果中，i类球放几个
if n==0: # n=0就是递归结束了，要放的球都安排好了～
Print(k, ans)
return
if n<0 or k==i:
return
for j in range(a[i]+1): # a[i]+1就是j可以取0～a[i]
# 即j表示这类球放几个
ans[i] = j
fun(i+1, n-j) # i+1是移动下，考虑放下一类球了～
ans[i] = 0 # 没遍历到的ans位就是放0个球
try:
while True:
line1 = sys.stdin.readline().strip()
l = list(map(int, line1.split()))
k = l[0] # 球共所少类
n = l[-1] # 共需要n个球
nums = sys.stdin.readlines()
# a数组，index为球的类，index上的value为这类球有的数量
a = [int(v.strip()) for v in nums]
fun(0, n)
except:
pass
|
[编程题]集合遍历
有K种颜色的小球(K<=10)，每种小球有若干个，总数小于100个。
现在有一个小盒子，能放N个小球(N<=8)，现在要从这些小球里挑出N个小球，放满盒子。
想知道有哪些挑选方式。注：每种颜色的小球之间没有差别。
请按数字递增顺序输出挑选小球的所有方式。
如有3种颜色，每种颜色小球的个数分别为a:1,b:2,c:3，挑出3个小球的挑法有：
003,012,021,102,111,120
输入描述:
第一行两个数字K N，分别表示小球种类数目和挑选的小球个数
第二行开始为每种小球的数目，共K行数据
输出描述:
输出所有可行的挑选方案，按升序排列
输入例子1:
3 3
1
2
3
输出例子1:
003
012
021
102
111
120
解法1：（c++）
| #include <iostream>
#include<vector>
#include<numeric>
using namespace std;
struct node{
int num;
vector<vector<int> > v;
};
int main(){
int K, N,Ki;
cin >> K >> N;
vector<node> ball(K);
for(int i=0;i<K;i++){
node p;
cin>>Ki;
ball[i].num=Ki;
}
if(K==1) cout<<N<<endl;
else {
vector<int> tmpv;
for(int i=0;i<=ball[0].num;i++) {
tmpv.push_back(i);
ball[0].v.push_back(tmpv);
tmpv.clear();
}
for(int i=1;i<K;i++){
for(int j=0;j<ball[i-1].v.size();j++){
for(int k=0;k<=ball[i].num;k++){
tmpv=ball[i-1].v[j];
tmpv.push_back(k);
if(i==K-1){
if(accumulate(tmpv.begin(),tmpv.end(),0)==N){
for(int l=0;l<tmpv.size();l++) cout<<tmpv[l];
cout<<endl;
}
}
else {
if(accumulate(tmpv.begin(),tmpv.end(),0)<=N) ball[i].v.push_back(tmpv);
}
tmpv.clear();
}
}
}
}
}
解法二（python）：
| import sys
K, N = list(map(int, sys.stdin.readline().split()))
def backtrace(i, my_dic, cnt, res, s):
if i == K and cnt == N:
res.append(''.join(s))
elif i < K:
for use in range(my_dic[i]+1):
if use <= N - cnt:
s.append(str(use))
backtrace(i+1, my_dic, cnt+use, res, s)
s.pop()
else:
break
if __name__ == '__main__':
my_dic = {}
for i in range(K):
my_dic[i] = int(sys.stdin.readline().strip())
res = []
backtrace(0, my_dic, 0, res, [])
for r in res:
print(r)
|
解法三（python）： # coding=utf-8
import sys
a = [0]*11
ans = [0]*11
k,n=0,0
def Print(k, ans):
res = ''
for i in range(k):
res += str(ans[i])
print(res)
def fun(i, n): # i可以认为是球类比的编号，ans[i]就是结果中，i类球放几个
if n==0: # n=0就是递归结束了，要放的球都安排好了～
Print(k, ans)
return
if n<0 or k==i:
return
for j in range(a[i]+1): # a[i]+1就是j可以取0～a[i]
# 即j表示这类球放几个
ans[i] = j
fun(i+1, n-j) # i+1是移动下，考虑放下一类球了～
ans[i] = 0 # 没遍历到的ans位就是放0个球
try:
while True:
line1 = sys.stdin.readline().strip()
l = list(map(int, line1.split()))
k = l[0] # 球共所少类
n = l[-1] # 共需要n个球
nums = sys.stdin.readlines()
# a数组，index为球的类，index上的value为这类球有的数量
a = [int(v.strip()) for v in nums]
fun(0, n)
except:
pass
|