Составить формулу на языке программирования

#алгоритм #математика #любой_язык

Не могу придумать как составить формулу, если A = 10, B = 25, C = 15, а R=40.
Нужно узнать сколько есть вариантов составить набор из элементов A,B,C ,чтобы сумма
их была именно равна R. В Данном случае 40.
То есть на этом примере ответом будет 3 т.к.


  
  A+A+A+A = R
  C+C+A = R
  B+C = R
  


А как это все записать формулу, чтобы программа считала сумму возможных вариантов?
    

Ответы

Ответ 1

Можно также решить рекурсией, но без полного перебора. 

Наши исходные A = 10, B = 25, C = 15, а R=40 можно представить в виде линейного уравнения

Ax+By+Cz=R

Теперь нам нужно найти все возможные варианты коэффициентов x,y,z доступные нам в
данном случае. Сделать это можно получив целое от деления R на А и потом инкрементно
получаем все возможные x, сохраняем. Повоторяем это для B и С. После уже запускаем
в рекурсии ищем возможные варианты.

Думаю если изучить методы решения систем линейных алгебраических уравнений можно
найти что то лучше.



r = 40;
a = [10,25,15];
b = [];
//находим коэффициенты
a.forEach(function(e,indx){
	i = parseInt(r/e);
	b[indx] = [];	
	while(i>=0){
		b[indx][b[indx].length]=i--;
		}
	});

out = [];
//ищем решения    
function recursion(i,sum=0,_sum=""){ 
	b[i].forEach(function(e, indx){
		sm=a[i]*e+sum;
    tmp = e>0?((_sum!=""?_sum+"+":"")+"("+a[i]+"*"+e+")"):_sum;
    if(sm==r){
      out[out.length]=tmp;
    	}
    else if( sm
Ответ 2

Такие задачи можно решать через рекурсию.

Смысл в том, что есть некая функция, которая получает в качестве аргумента число R.
После этого она перебирает числа A, B, C, ...
Каждое из этих чисел она вычитает из R.

Если получилось число меньше нуля - это тупиковая ветвь, её мы отбрасываем.
Если ровно ноль - мы нашли одно из решений, записываем его в специальный массив для
результатов.
Если получилось число больше нуля - мы вызываем эту же функцию, но уже не с аргументом
R, а с получившимся остатком.
В результате, программа будет по цепочке пытаться вычитать из исходной целевой суммы
разные наборы из чисел A, B, C, ... и находить такие варианты этих наборов, которые
полностью укладываются в R.

Вот вариант на питоне:

glob_res = []

def recursion(r, lst, res=None):
    """
    Функция получает в качестве аргументов целевую сумму R
        и список из слагаемых A, B, C и т.д.
    res - это список отобронных слагаемых, который будет передаваться по цепочке
        дочерним функциям
    При первом вызове он пуст, а потом будет накапливаться
    """

    for arg in lst:

        if res == None:
            cur_res = []
        else:
            cur_res = res[:]

        remain = r - arg
        if remain == 0:
            cur_res.append(arg)
            glob_res.append(cur_res)
        if remain > 0:
            cur_res.append(arg)
            recursion(remain, lst, cur_res[:])

if __name__ == '__main__':
    recursion(40, [10, 25, 15])
    print(glob_res)


Программа выведет:

[[10, 10, 10, 10], [10, 15, 15], [25, 15], [15, 10, 15], [15, 25], [15, 15, 10]]


Вам осталось только взять длину этого списка - сколько в нём элементов, такой и ваш
ответ.

Примечание: Как видно, программа находит все подходящие комбинации. Варианты, в которых
те же слагаемые, но по разному расположены, она считает за разные варианты, и выводит
их отдельно.

Если нужно, чтобы она рассматривала их как тот же вариант и выводила только один
раз, есть два пути:


Уже после отрабатывания всей рекурсии фильтровать результат.
Либо при работе рекурсии если в какой-то её ветке мы отработали один аргумент и перешли
к следующему, то потомкам этой ветки передавать массив lst без этого слагаемого (для
этого и нужно его вообще передавать, иначе можно было просто один раз глобально массив
слагаемых объявить). Но эти тонкости я оставляю вам для самостоятельного разбора :)


Если что непонятно - гуглите "рекурсия".


Ответ 3

Вот пример программы, которая перебирает всевозможные комбинации операций над кортежем
из чисел от 1 до 9, с тем условием, что в итоге мы получим какое-то конкретное число.
Написана на F#, юзает CUDA, очень быстрая(!). Раз Вам интересны такие вещи - то эта
штука Вам обязательно понравится. Да и можно ее перепелить под свои нужды. Хотя, Отморский
может остаться недоволен Вашим качеством кода.. ;)


Ответ 4

вариант решения для массива неповторяющихся чисел, иначе зациклится.



function fn(d, b) {
  b = b.slice(0).sort(function(a, b) {
    return a - b
  });
  for (var a = [], e = []; a[0] != b.slice(-1);) {
    var c = a.reduce(function(a, b) {
      return a + +b
    }, 0);
    c < d ? a.push(b[0]) : (c == d && e.push(a.slice(0)), a.pop(), c = a[a.length
- 1], c = b.indexOf(c), a[a.length - 1] = b[++c])
  }
  return e
};
console.log(fn(40,[10,25,15]))