Alexander A Manaeff -

 
 

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

программирование на современных языках программирования: Java, C, C++, C#

Модератор: UncleFather

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

Сообщение UncleFather » 09 сен 2016 14:43, Пт




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

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

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

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

Итак, для подсчета количества разбиений числа, воспользуемся рекуррентной формулой из Википедии (см. ссылку выше):
01.jpg
01.jpg (7.07 КБ) Просмотров: 2507
с начальными значениями:
02.jpg
02.jpg (4.55 КБ) Просмотров: 2507


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©

Понравилась статья? Будем крайне признательны за репосты в соцсетях! Материально поддержать проект можно здесь

Мои странички:
ВКонтакте
Одноклассники
Youtube
Facebook
Instagram
Изображение
Изображение
Изображение
Изображение
Аватара пользователя
UncleFather
Site Admin
 
Сообщения: 1411
Зарегистрирован: 17 авг 2004 16:20, Вт



Вернуться в Java, C, C++, C#

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Alexander A Manaeff -
@Mail.ru .