首页 > 试题广场 >

科室素拓活动

[编程题]科室素拓活动
  • 热度指数：1670 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
科室素拓进行游戏，游戏规则如下：随机抽取9个人作为游戏参与人员，分别编号1至9，每轮要求k(k<=9且k>=0)个人自由组合使编号之和为n。输出满足规则的所有可能的组合。要求组合内部编号升序输出，组合之间无顺序要求。

输入描述:
输入数据为以空格分隔的两个整数k和n


输出描述:
每行输出一个可能的编号组合，组合内部各个编号以空格分隔升序输出。若无满足规则的组合，则输出None
示例1

输入

3 15

输出

1 5 9
1 6 8
2 4 9
2 5 8
2 6 7
3 4 8
3 5 7
4 5 6
算法知识视频讲解
添加回答
向宇回桌头像 向宇回桌 
import java.util.*;

public class Main {
    public static int k, n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt(); n = sc.nextInt();
        dfs(1, 0, k, 0);
        if (flag) {
            System.out.println("None");
        }
    }
    static boolean flag = true;
    private static void dfs(int cur, int ans, int k, int mem) {
        if (ans == n && k == 0 ) {
            StringBuilder sb = new StringBuilder();
            for (int i=1; i<=9; i++) {
                if (((mem >> i) & 1) == 1) {
                    sb.append(i);
                    sb.append(" ");
                }
            }
            System.out.println(sb.toString());
            flag = false;
            return;
        }
        if (k < 0 || cur > 9 || ans > n) { return; }
        dfs(cur+1, ans+cur, k-1, mem | (1<<cur));
        dfs(cur+1, ans, k, mem);
    }
}
编辑于 2019-03-05 16:17:31 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> r;
vector<int> v;

void DFS(int k, int n, int s){
    if(k==0){
        if(n==0)
            r.push_back(v);
        return;
    }
    if(10-s < k)
        return;
    for(int i=s;i<=9;i++){
        v.push_back(i);
        DFS(k-1, n-i, i+1);
        v.pop_back();
    }
}

int main(){
    int k, n;
    scanf("%d%d", &k, &n);
    DFS(k, n, 1);
    if(r.empty())
        puts("None");
    else{
        for(int i=0;i<r.size();i++)
            for(int j=0;j<k;j++){
                if(j==k-1)
                    printf("%d\n", r[i][j]);
                else
                    printf("%d ", r[i][j]);
            }
    }
    return 0;
}

发表于 2020-10-25 01:29:41 回复(0)
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    static int k;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        k = Integer.parseInt(strs[0]);
        n = Integer.parseInt(strs[1]);

        if (k == 0 || n > 45 || n <= 0) {
            System.out.println("None");
            return;
        }

        int[] res = new int[k];
        boolean[] flag = {true};
        generate(0, 1, res, 0, flag);
        if (flag[0]) System.out.println("None");
    }

    private static void generate(int cur, int start, int[] res, int sum, boolean[] flag) {
        if (cur == k && sum == n) {
            flag[0] = false;
            for (int i = 0; i < k - 1; i++) {
                System.out.print(res[i] + " ");
            }
            System.out.println(res[k - 1]);
            return;
        }
        if (cur == k || sum > n) return;

        for (int i = start; i <= 9; i++) {
            res[cur] = i;
            generate(cur + 1, i + 1, res, sum + i, flag);
        }
    }
}

编辑于 2019-01-24 21:14:16 回复(0)
LY_Zilean头像 LY_Zilean
我来组成全部c#答案 !

using System;
using System.Collections.Generic;
public class Program {
    public static void Main() {
        string line;
        while ((line = System.Console.ReadLine ()) != null) { // 注意 while 处理多个 case
            string[] tokens = line.Split();
            int k = int.Parse(tokens[0]);
            int n = int.Parse(tokens[1]);

            if(k==1 && n<=9)
            {
                Console.WriteLine(n);
                continue;
            }
            int res = 0;
            for(int i=9;i>=1;i--)
            {
                int[] arr = new int[k];
                arr[k-1] = i;
                res += Rule(k-1, n-i, arr);
            }
            if(res == 0)
            {
                Console.WriteLine("None");
            }
        }
    }

    public static int Rule(int k,int n,int[] arr)
    {  
        if(n<1)
            return 0;
        if(k==1)
        {
            if(n<arr[k])
            {
                string str = n.ToString();
                for(int i=1;i<arr.Length;i++)
                {
                    str = str + " " +arr[i];
                }
                Console.WriteLine(str);
                return 1;
            }
            else
                return 0;
        }

        int res = 0;
        for(int i=1;i<9 && i<n;i++)
        {
            if(i < arr[k])
            {
                arr[k-1] = i;
                res += Rule(k-1, n-i,arr);
            }
            else
            {          
                break;
            }
        }
        return res;
    }
}

发表于 2023-11-29 23:24:55 回复(0)
Python
rika0613头像 rika0613 
n,target = list(map(int,input().split()))
candidates = [1,2,3,4,5,6,7,8,9]
result = []

def dfs(remain,stack):
    if remain == 0 and len(stack)==n:
        result.append(stack)
        return
        
    for item in candidates:
        if item > remain:
            break
        if stack and item <= stack[-1]:
            continue
        else:
            dfs(remain-item,stack+[item])
            
dfs(target,[])
if result:
    for i in result:
        for j in i:
            print(j,end=' ')
        print('')
else:
    print('None')
递归算法
编辑于 2018-11-07 01:01:01 回复(1)
callofdutyops头像 callofdutyops
思路很简单，1~9的k组合数，若组合数之和等于n，则输出。非递归代码如下： 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Scanner cin = new Scanner(System.in);
        int k = cin.nextInt();
        int n = cin.nextInt();
        String result = getResult(k, n, arr);
        System.out.print(result);
    }
 
    private static String getResult(int k, int n, int[] arr) {
        StringBuilder result = new StringBuilder();
 
        LinkedHashSet<int[]> combinations = getCombination(arr, k);
        if (combinations != null) {
            //对每一组合进行判断
            for (int[] combination : combinations) {
                if (Arrays.stream(combination).sum() == n) {
                    for (int i : combination) {
                        result.append(i);
                        result.append(" ");
                    }
                    result.deleteCharAt(result.length() - 1);
                    result.append("\n");
                }
            }
            if (result.length() > 1) {
                result.deleteCharAt(result.length() - 1);
            }
        }
        if (result.length() == 0) {
            result.append("None");
        }
 
        return result.toString();
    }
 
    //返回组合数
    public static LinkedHashSet<int[]> getCombination(int[] input, int selectNum) {
        int inputLen = input.length;
 
        LinkedHashSet<int[]> result = new LinkedHashSet<>();
        if ((inputLen == 0) || inputLen < selectNum) {
            return null;
        }
        if (inputLen == selectNum) {
            result.add(input);
            return result;
        }
 
        int[] itemIndex = new int[selectNum];
 
        for (int i = 0; i < selectNum; i++) {
            itemIndex[i] = i;
        }
 
        int index = selectNum - 1;
        while (index >= 0) {
            int[] resultItem = new int[selectNum];
            for (int j = 0; j < selectNum; j++) {
                resultItem[j] = input[itemIndex[j]];
            }
 
            result.add(resultItem);
            while (itemIndex[index] == inputLen - (selectNum - index)) {
                if (--index < 0) {
                    return result;
                }
            }
            if (itemIndex[index] < inputLen - (selectNum - index)) {
                ++itemIndex[index];
                for (int a = 0; a < selectNum - index - 1; a++) {
                    itemIndex[index + a + 1] = itemIndex[index] + a + 1;
                }
                index = selectNum - 1;
            }
        }
        return result;
    }
}

编辑于 2018-08-30 16:40:35 回复(0)
田野之雪头像 田野之雪 
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main{
    public static int k;
    public static int n;
    
    
    public static int[] oneRes;
    public static List<String> res;
    
    public static void solve(int h, int i,int sum){
        if(sum>n) return;
        if(h==k&&sum==n ){
            String curS="";
            for(int jj=0;jj<k;++jj){
                curS+=oneRes[jj]+" ";
            }
            res.add(curS.trim());
        }
        if(h==k) return;       
       
        for(int j=i+1;j<=9;++j){
            oneRes[h]=j;
            sum+=j;
            solve(h+1,j,sum);
            sum-=j;
        }        
        
    }
    
    public static void main(String[] argv){
        Scanner sc=new Scanner(System.in);
        
        while(sc.hasNextInt()){
            k=sc.nextInt();
            n=sc.nextInt();
            if(k==0||n==0) {System.out.println("None");continue;}
                        
            
            oneRes=new int[k];   
            res=new ArrayList<String>();
            solve(0,0,0);
            if(res.size()==0){System.out.println("None");}
            else{
                for(String s:res){
                    System.out.println(s);
                }
            }
        }
        sc.close();
    }
}

发表于 2018-08-30 15:28:13 回复(0)
kyan头像 kyan 
#思想 回溯法  并加上一些判断提前结束递归的条件
class Solution():
    def __init__(self):
        self.k, self.n = list(map(int, input().split(' ')))
        self.result = []

    def track(self, data, path):
        if not data:
            return 0
        if len(data) == 9 - self.k and sum(path) == self.n:
            t=sorted(path)
            if t not in self.result:
                self.result.append(t)
            return 0
        if len(data) < 9 - self.k or sum(path) > self.n:
            return 0
        for i in range(len(data)):
            self.track(data[:i]+data[i + 1:], path + [data[i]])

    def run(self):
        if self.k == 9 and self.n == 45:
            print(' '.join([str(i) for i in range(1, 10)]))
            return 0
        elif self.n > 45 or self.k <= 0:
            print('None')
        else:
            self.track([i for i in range(1, 10)], [])
            if not self.result:
                print('None')
            else:
                for u in self.result:
                    print(' '.join([str(i) for i in u]))


if __name__ == '__main__':
    Solution().run()

发表于 2018-08-30 14:00:11 回复(0)
Raywall头像 Raywall 
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void help(vector<vector<int>>& res,vector<int> gp,int num,int left,int index)
{
    if(num<=0)
        return;
    for(int i=index;i<=9;i++)
    {
        if(i<left&&num>0)
        {
            gp.push_back(i);
            help(res,gp,num-1,left-i,i+1);
            gp.pop_back();
        }
        else if(i==left&&num==1)
        {
            gp.push_back(i);
            res.push_back(gp);
            return;
        }
        else
            return ;
    }
    return ;
}
 
int main()
{
    int k,n;
    cin>>k>>n;
    vector<vector<int>> res;
    vector<int> tmp;
    help(res,tmp,k,n,1);
    int len=res.size();
    if(len!=0)
    {
        for(int i=0;i<len;i++)
        {
            for(int j=0;j<k-1;j++)
                cout<<res[i][j]<<" ";
            cout<<res[i][k-1]<<endl;
        }
    }
    else
        cout<<"None";
    return 0;
}

发表于 2018-08-15 20:36:20 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 PHP工程师 穷举 2018 数学 大数据开发工程师 招商银行信用卡中心 Java工程师
上传者：小小
难度：
9条回答 2947浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号