Alexander A. Manaeff

**UncleFather** » 09 сен 2016 14:43, Пт

Java, разбиениe числа на слагаемые

Задача 1. Выведем количество разбиений числа

Примечание: Разбиение числа n — это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается.

Не путаем разбиение с композицией!

Итак, для подсчета количества разбиений числа, воспользуемся рекуррентной формулой из Википедии (см. ссылку выше):

: 01.jpg (7.07 КБ) 4525 просмотров

с начальными значениями:

: 02.jpg (4.55 КБ) 4525 просмотров

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.

Alexander A. Manaeff

Java, разбиениe числа на слагаемые

Ответить

Развернуть Обзор темы: Java, разбиениe числа на слагаемые

Java, разбиениe числа на слагаемые