자연수 n,m을 입력받아서 n이 m개의 자연수들의 합으로 표현될 때
그 경우의 수와 // 그 때의 자연수들 쌍을 출력하는 프로그램을 작성하시오.
ex) 입력 : 6 3 경우의 수 : 3 자연수들 쌍 : [4,1,1] [3,2,1] [2,2,2]
13개의 풀이가 있습니다.
from itertools import combinations_with_replacement as H
def DIVID(n,m):
A=[list(x) for x in H(range(1,n),m) if sum(x)==n]
print('{0}/{1}'.format(len(A), str(A)[1:-1]))
ex) DIVID(10, 4) 9/[1, 1, 1, 7], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 2, 2, 5], [1, 2, 3, 4], [1, 3, 3, 3], [2, 2, 2, 4], [2, 2, 3, 3]
Python 3.x
# 재귀함수 이용
def Divide(a, b, start): # start는 분할에서 처음에 빼기 시작하는 수
r_lst = []
if b != 1: # a에서 start를 뺀 후 남은 수를 마저 분할, 이후 start에 1씩 더해가며 반복
for s in range(start, int(a / b) + 1):
div_lst = Divide(a - s, b - 1, s)
for lst in div_lst: # 마저 분할한 각 list를 s와 합친다
r_lst.append([s] + lst)
else: # b가 1이면 a만 list에 담아 return
r_lst.append([a])
return r_lst
# 결과 출력함수
def P(n, m):
result = Divide(n, m, 1)
l = len(result)
print(l, "/", str(result)[1 : -1])
# ex)
# P(8, 3)
# 5 / [1, 1, 6], [1, 2, 5], [1, 3, 4], [2, 2, 4], [2, 3, 3]
from itertools import product
def GetSolution(m, n):
"""
Return all solutions of length 'n' without duplication.
m, n: natural number, m >= n
ex) GetSolution(6, 3)
"""
assert type(m) == int and type(n) == int
assert m >= n
# Get solutions
s = list(range(1, m + 1))
result = [r for r in product(s, repeat=n) if sum(r) == m]
# Get duplications
temp = []
for r in result:
count = 0
for i in range(len(r) - 1):
if r[i] > r[i+1]:
count += 1
if count:
temp.append(r)
# Remove duplications
for i in temp:
result.remove(i)
print('The number of solutions: {}'.format(len(result)))
return result
solution n m = solution' n m n
where
solution' 0 0 _ = [[]]
solution' _ 0 _ = []
solution' n m b = do
i <- [b, b-1 .. 1]
rest <- solution' (n-i) (m-1) i
pure $ i : rest
역시 recursion입니다. 맨 앞의 숫자를 정해놓고, 나머지들을 다시 돌리는거죠.
def GetLists(preList:list, targetNum:int, nComp:int):
if (nComp==1):
preList.append(targetNum)
print(preList)
else:
for i in range(1,targetNum-nComp+2):
theList = preList.copy()
theList.append(i)
GetLists(theList, targetNum-i, nComp-1)
InputStr = input("n>m인 두 수를 칸을 띄워 입력하시오: ")
InputList = InputStr.split(' ')
N = int(InputList[0])
M = int(InputList[1])
GetLists([], N, M)
from itertools import combinations_with_replacement
def factorize_natural_number(n, m):
"""
자연수 n, m을 입력받아서 n이 m개의 자연수들의 합으로 표현합니다.
-----------------------------------------------------
return
1. 경우의 수
2. 자연수들 쌍
"""
pairs = combinations_with_replacement(range(1, n), m)
result = [pair for pair in pairs if sum(pair) == n]
return len(result), result
# Example
num, result = factorize_natural_number(6, 3)
print("경우의 수: {}".format(num))
print("자연수들 쌍: {}".format(result))
import itertools
q = int(input("숫자 입력 : "))
w = list(range(1,q))
n = int(input("쌍 : "))
a=[]
c=[]
result = list(itertools.product((w), repeat=n)) # 중복순열
for i in result:
total=0
for j in i:
total+=int(j)
if total== q :
a.append(i)
for i in a:
c.append(sorted(list(i)))
print(len(list(set(map(tuple,c)))))
print(list(set(map(tuple,c))))
package justStudying;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
public class test1_20210808 {
public static PriorityQueue<String> mB = new PriorityQueue<>();
//chk
public static void chk(int n, int m, int max, ArrayList<Integer> f) {
//선택한 자연수 갯수가 m개이고 && 선택한 자연수들의 합이 n일때
if(f.size() == m && max == n) {
ArrayList<Integer> tempA = (ArrayList<Integer>)f.clone(); //복사하여 사용!!
Collections.sort(tempA, new Comparator<Integer>() { // 오름차순 셋팅하여 중복방지 체크
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1.compareTo(o2);
}});
String temp = "";
for(int i=0; i<tempA.size(); i++) {
temp += tempA.get(i);
}
if(mB.contains(temp)) {} //중복 방지를 위함
else mB.add(temp); //중복되지 않은 경우 추가
}
// 선택한 자연수 갯수가 m개 미만이고 && 선택한 자연수들의 합이 max를 넘지 않을때
else if(f.size() < m && max < n) {
for(int i=1; i<=n; i++) { //모든 경우를 체킹
f.add(i); // 선택
chk(n,m, max+i, f); //선택한 경우의 수
f.remove(f.size()-1);//선택 해제
}
}
}
public static void sol(int n, int m) {
chk(n,m,0,new ArrayList<Integer>());
while(!mB.isEmpty()) {
System.out.println(mB.poll());
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
sol(6,3);
}
}
from itertools import combinations_with_replacement as cr
a,b = map(int,input("숫자입력: ").split())
hap = []
for i in cr(range(1,a),b):
if sum(i) == a:
hap.append(i)
print(len(hap),hap)
// Rust
// m개 자연수 중 가장 큰 수를 n0라 할때, n0가 가능한 범위를 우선 구하고,
// n0 값별로, m-1개 자연수의 합이 n-n0인 배열을 구하는 문제이므로
// 재귀함수를 돌렸습니다
fn sum_natural_numbers() {
let n = 6;
let m = 3;
println!("{:?}", recur_array(n, m));
}
fn recur_array(n: usize, m: usize) -> Vec
if m == 1 { return vec![vec![n]];}
let n0_max = n - m + 1;
let n0_min = if n % m == 0 { n / m } else { n / m + 1 };
let mut result = vec![];
for n0 in (n0_min..=n0_max).rev() {
for v in recur_array(n-n0, m-1) {
if n0 < v[0] { continue; }
let mut vec = vec![n0];
vec.extend(v);
result.push(vec);
}
}
result
}
from itertools import combinations_with_replacement as H
n = int(input("더했을 때의 결과? : "))
m = int(input("몇 개를 더할 것인가? : "))
li = [list(x) for x in H(range(1, n), m) if sum(x) == n]
print("경우의 수 : {}, 자연수들의 쌍 : {}" .format(len(li), li))
import java.util.ArrayList;
import java.util.Comparator;
import java.util.ListIterator;
import java.util.Scanner;
public class DivisionOfNumber {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
ArrayList<Integer> coupleForTest = new ArrayList<>();
public static void main(String[] args) {
DivisionOfNumber divisionOfNumber = new DivisionOfNumber();
Scanner scan = new Scanner(System.in);
int number, size;
while(true) {
System.out.print("Enter number : ");
number = scan.nextInt();
System.out.print("Enter size : ");
size = scan.nextInt();
if(number<2) {
System.out.println("The number entered is less than 2.");
}else if(size<2) {
System.out.println("The size entered is less than 2.");
}else {
break;
}
}
divisionOfNumber.initialization(size);
divisionOfNumber.findCouple(number, size);
divisionOfNumber.printList();
}
private void initialization(int size) {
for(int i=0; i<size; i++) {
coupleForTest.add(1);
}
}
private void findCouple(int number, int size) {
while(coupleForTest.get(0)<=Math.sqrt(number)) {
coupleForTest.set(size-1, coupleForTest.get(size-1)+1);
ListIterator<Integer> iter1 = coupleForTest.listIterator(size);
while(iter1.hasPrevious()) {
int element = iter1.previous();
if(iter1.nextIndex()!=size-1) {
element += 1;
}
if(element==number) {
iter1.set(1);
}else {
iter1.set(element);
break;
}
}
int sum = 0;
ListIterator<Integer> iter2 = coupleForTest.listIterator(0);
while(iter2.hasNext()) {
sum += iter2.next();
}
if(sum == number) {
ArrayList<Integer> newCouple = checkSameElement(coupleForTest);
if(newCouple==null)
continue;
else
list.add(newCouple);
}
}
}
private void printList() {
System.out.print("Result ->");
for(int i=0; i<list.size(); i++) {
System.out.print(printString(list.get(i)));
if(i!=list.size()-1)
System.out.print(" ,");
}
System.out.println();
}
public String printString(ArrayList<Integer> couple) {
String result = " {";
for(int i=0; i<couple.size(); i++) {
result += couple.get(i);
if(i!=couple.size()-1)
result+=", ";
}
result += "}";
return result;
}
private ArrayList<Integer> checkSameElement(ArrayList<Integer> couple) {
ArrayList<Integer> copy = new ArrayList<>();
for(int i=0; i<couple.size(); i++) {
copy.add(couple.get(i));
}
copy.sort(Comparator.reverseOrder());
ListIterator<ArrayList<Integer>> iter = list.listIterator();
while(iter.hasNext()) {
if(iter.next().equals(copy))
return null;
}
return copy;
}
}
ArrayList로 풀어보았습니다.
def divisionOfNaturalNumbers(cnt, num, hap, A):
if cnt == 1:
if n-hap >= num:
A.append(n-hap)
res.append(A)
return
for i in range(num, (n-hap)//cnt + 1):
A.append(i)
B = A.copy()
divisionOfNaturalNumbers(cnt-1, i, hap + i, B)
A.pop(-1)
n = 6
m = 3
res = []
divisionOfNaturalNumbers(m, 1, 0, [])
print(res)