Java, разбиениe числа на слагаемые
Java, разбиениe числа на слагаемые
Задача 1. Выведем количество разбиений числа
Не путаем разбиение с композицией!
Итак, для подсчета количества разбиений числа, воспользуемся рекуррентной формулой из Википедии (см. ссылку выше):
с начальными значениями:
java:
Код: Выделить всё
import java.util.Scanner;
public class Slagaemye {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int iVol = sc.nextInt();
System.out.println(slag(iVol , iVol));
}
static int slag(int n, int k) {
if (n > 0 && k == 0) return 0;
if (n == 0 && k == 0) return 1;
if (k > n) return slag(n, n);
return slag(n, k-1) + slag(n-k, k);
}
}
Задача 2. Выведем количество разбиений числа для неповторяющихся слагаемых
Алгоритм аналогичен предыдущей задаче, за исключением одного из рекурсивных вызовов в последней строке.
java:
Код: Выделить всё
import java.util.Scanner;
public class Slagaemye_nepovtor {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int iVol = sc.nextInt();
System.out.println(slag(iVol , iVol));
}
static int slag(int n, int k) {
if (n > 0 && k == 0) return 0;
if (n == 0 && k == 0) return 1;
if (k > n) return slag(n, n);
return slag(n, k-1) + slag(n-k, k-1);
}
}
Задача 3. Выведем все разбиения числа
java:
Код: Выделить всё
import java.util.Scanner;
public class Slagaemye {
static int[] iArr = new int[100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int iVol = sc.nextInt();
currSlag(iVol, iVol, 0);
}
static void currSlag(int n, int k, int i) {
if ( n < 0 ) return;
if ( n == 0 ) {
for (int j = 0; j < i; j++) System.out.print(iArr[j] + " ");
System.out.println();
}
else {
if ( n >= k) {
iArr[i] = k;
currSlag(n - k, k, i + 1);
}
if ( k > 1) currSlag(n, k - 1, i);
}
}
}
Задача 4. Выведем все разбиения числа с неповторяющимися слагаемыми
Опять же, предыдущий алгоритм почти полностью сохраняется, за исключением первого условия и одного из рекурсивных вызовов в процедуре.
java:
Код: Выделить всё
import java.util.Scanner;
public class Slagaemye_nepovtor {
static int[] iArr = new int[100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int iVol = sc.nextInt();
currSlag(iVol, iVol, 0);
}
static void currSlag(int n, int k, int i) {
if ( n < 0 || k < 0 ) return;
if ( n == 0 ) {
for (int j = 0; j < i; j++) System.out.print(iArr[j] + " ");
System.out.println();
}
else {
if ( n >= k) {
iArr[i] = k;
currSlag(n - k, k - 1, i + 1);
}
if ( k > 1) currSlag(n, k - 1, i);
}
}
}
По данной теме дополнительно смотрим статью в разделе «олимпиады по программированию на Физтехе» на сайте МФТИ Лекция 6. Задача разложения числа на слагаемые. Задача подсчета и генерации и обсуждение Разложение числа на неповторяющиеся слагаемые на сайте CyberForum.ru.