Разбиване на числа
5 отговора
238 прегледа
Разбиване на числа
Здравейте! Пускам тази тема в "Математика" и в "Логика". Занимавам се любителски с програмиране и стигнах до следния проблем: нуждая се от формула (метод) за получаване на всички варианти на разбиване на сума S на p броя различни неповтарящи се събираеми в областта на реалните положителни числа. Не знам доколко задавам условието достатъчно издържано, затова давам пример: сума 100 трябва да разбия на 3 числа. а + б + с = 100. Търся всички а, б, с (а =/= б =/= с), чиито сбор дава 100.
Re: Разбиване на числа
Ами не е толкова сложно. Нека подредим събираемите а>б>с. В един цикъл извърташ всички възможни а: от 35 до 97 включително (защо 35 и 97, сигурно се сещаш - нали трите събираеми трябва да са различни и а да е най-голямото). Вътре влагаш втори цикъл за б, който въртиш от (102-а)/2 (при четно а) или от (101-а)/2 (при нечетно а) до 99-а. Накрая пресмяташ с като 100-а-б и готово.
Сравнително лесно можеш да си го обобщиш за други суми и друг брой събираеми. Нека сумата е С, а събираемите са н на брой естествени числа: х1+х2+...+хн=С, х1>х2>...>хн>0.
Най-външният цикъл е: х1 от (2*(С-1)+н*(н+1)))/(2*н) до С-н*(н-1)/2 включително. Делението е целочислено, като остатъкът (ако има такъв) се пренебрегва.
Границите за следващите (вложени) цикли се пресмятат по същата формула, но вместо С се взема остатъкът (за втория цикъл по х2 например това ще е С-х1) и вместо н - броят на оставащите неопределени събираеми.
Пример: нека С=100, н=5.
Цикъл по х1: работим с С=100, н=5. Границите са от (2*(100-1)+5*(5+1)))/(2*5)=22 до 100-5*(5-1)/2=90 включително.
Цикъл по х2: работим с С=100-х1, н=4. Границите са от (2*(100-х1-1)+4*(4+1)))/(2*4) до 100-х1-4*(4-1)/2 включително.
Цикъл по х3: работим с С=100-х1-х2, н=3. Границите са от (2*(100-х1-х2-1)+3*(3+1)))/(2*3) до 100-х1-х2-3*(3-1)/2 включително.
Цикъл по х4: работим с С=100-х1-х2-х3, н=2. Границите са от (2*(100-х1-х2-х3-1)+2*(2+1)))/(2*2) до 100-х1-х2-х3-2*(2-1)/2 включително.
Накрая: х5=100-х1-х2-х3-х4.
Успех!
Сравнително лесно можеш да си го обобщиш за други суми и друг брой събираеми. Нека сумата е С, а събираемите са н на брой естествени числа: х1+х2+...+хн=С, х1>х2>...>хн>0.
Най-външният цикъл е: х1 от (2*(С-1)+н*(н+1)))/(2*н) до С-н*(н-1)/2 включително. Делението е целочислено, като остатъкът (ако има такъв) се пренебрегва.
Границите за следващите (вложени) цикли се пресмятат по същата формула, но вместо С се взема остатъкът (за втория цикъл по х2 например това ще е С-х1) и вместо н - броят на оставащите неопределени събираеми.
Пример: нека С=100, н=5.
Цикъл по х1: работим с С=100, н=5. Границите са от (2*(100-1)+5*(5+1)))/(2*5)=22 до 100-5*(5-1)/2=90 включително.
Цикъл по х2: работим с С=100-х1, н=4. Границите са от (2*(100-х1-1)+4*(4+1)))/(2*4) до 100-х1-4*(4-1)/2 включително.
Цикъл по х3: работим с С=100-х1-х2, н=3. Границите са от (2*(100-х1-х2-1)+3*(3+1)))/(2*3) до 100-х1-х2-3*(3-1)/2 включително.
Цикъл по х4: работим с С=100-х1-х2-х3, н=2. Границите са от (2*(100-х1-х2-х3-1)+2*(2+1)))/(2*2) до 100-х1-х2-х3-2*(2-1)/2 включително.
Накрая: х5=100-х1-х2-х3-х4.
Успех!