Подбор чисел,чтобы вышла определенная сумма в Си

[Вероника99]

Есть массив из 8 чисел
int rest[12]={20,10,10,5,3,2,1,1};
нужно сделать новый массив из 6 элементов с помощью перестановок так,чтобы получилось число 71
Я не знаю,как такое сделать((((((

[Vanta11a]

В чем суть перестановок?
Потому что перестановки не предполагают объединения/замены элементов.
Как вычисляется 71? Сумма элементов?

[Bugrimov]

Я честно говоря тоже ничего не понял.... Опишите задание по подробнее..

[Serge_Bliznykov]

включаю телепатор...

в связи с тем, что сумма ВСЕХ элементов заданного набора составляет 52,
то:
либо насчёт 71 автор топика ошиблась,
либо речь идёт о банальном разбиении денежной суммы на представленные номиналы купюр (причём, нужно получить ВСЕ возможные варианты представления суммы.
ну, например, для суммы = 4
это варианты:
1+1+1+1
2+1+1
2+2

И, предполагаю, что в таком случае порядок не важен (ну 2+1+1 то же самое, что 1+2+1 )


p.s. резонно возразить, что если в наборе представлены НОМИНАЛЫ, каждый из которых может быть использован не ограниченное число раз, то зачем в наборе по ДВАЖДЫ представлены номиналы 10 и 1. Ну это может быть банальной ошибкой. А может быть, там задумано, чтобы усложнить задачу...

p.p.s. на истину не претендую, просто предположение сделал

[Smitt&Wesson]

Сообщение от Вероника99

Есть массив из 8 чисел
int rest[12]={20,10,10,5,3,2,1,1};
нужно сделать новый массив из 6 элементов с помощью перестановок так,чтобы получилось число 71
Я не знаю,как такое сделать((((((

1. Сумма всех чисел последовательности из 8-и элементов, даёт число = 52-м. Явно, что последовательность из 6-и цифр, даст меньшее число. В данном случае, задача решения не имеет.
2. Для чего, для последовательности состоящей из 8-ми чисел, зарезервирован массив из 12-и элементов?
3. В условии не указано, можно ли использовать одно и то-же число шесть раз подряд, или можно использовать только имеющуюся последовательность?
Ответьте на эти вопросы, и мы постараемся Вам помочь.
Ну и по теме. Если в условии выполняется пункт 3. Формула для расчёта такая:
!6 * !8 = 29030400 комбинаций перестановок.
Для полного перебора, необходимо 14-ть вложенных циклов. Учитывая, что один цикл выполняется 1 мсек (0,001с) = 29030 с или 484 минуты или 8 часов непрерывного счёта.

[Вероника99]

А да сорри, я забыла написать что изначально в новом массиве, в который будут заносится подходящте числа уже есть 50

[Вероника99]

Сообщение от Smitt&Wesson

2. Для чего, для последовательности состоящей из 8-ми чисел, зарезервирован массив из 12-и элементов?

Там походу программы в этом массив надо будет заносить еще числа, это все качается той задачи с мишенями,которую я в другой теме скидывала

[Вероника99]

Вот что получилось,бредятина, не знаю,что делать

int CreateArray1(int *r)
{
	int i=0,j,k,j2,j3,j4,j5,sum=50;
	for(i=0;i<9;i++) //25
	{
	for(j=8;j>=(i+5);j--) 
		for(j2=7;j2>=(i+5);j2--)
			for(j3=6;j3>=(i+5);j3--)
				for(j4=5;j4>(i+5);j4--)
				
		{	

			sum+=r[i]+r[j]+r[j2]+r[j3]+r[j4];
			if(sum==71)
			{
				for(k=1;k<=6;)	
				{	
					k++;
					first[k]=r[j++];
	 			}
	    	
			}	
				
		}
	printf("%i\n",sum);
		sum=0;//чтобы не прибавлялось к предыдущей сумме
	}

	return 0;
}

[Rin]

ТС нужно выбрать из 8 элементов пять, чтобы при сложении с числом 50 получить в итоге 71. Если брать приведенный ею выше массив {20,10,10,5,3,2,1,1}, то нам понадобится 10+5+3+2+1 +50 =71. В общем получится 4 ответа(т.к. у нас две "10" и две "1"), которые по этому требованию подходят.

Здесь не перестановки нужны, а сочетания. Получается С из 8 по 5 = 56 сочетаний, так что никаких 8 часов на раздумья компа не нужно. Формула есть в вики, если кто не помнит или не проходил. Вот алгоритм генерации сочетаний, но он на pascal'e. А я уже изрядно измучен, поэтому не смогу сейчас вам чем-то существенным помочь:

begin
  for i := 1 to k do
    A[i] := i; //Первое подмножество
  p := k;
  while p >= 1 do
  begin
    writeln(A[1],..., A[k]); //вывод очередного сочетания
    if A[k] = n then
      p := p - 1
    else
      p := k;
    if p >= 1 then
      for i := k downto p do
        A[i] := A[p] + i - p + 1;
  end;
end;

Авторство не мое. Код из книги "Липский В. «Комбинаторика для программистов», М., Мир, 1988"

[Poma][a]

Пока так..

#include <stdio.h>
#define n 5
#define ans 71
#define size 8

int a[size] = {20, 10, 10, 5, 3, 2, 1, 1}, b[size];

void p(int sum, int k, int pos)
{
	int flag;
	if (n == k)	
	{
		if (sum+50 == ans)
		{	printf("50 + ");	
			for (int i = 0; i < n-1; i++)
				printf("%d + ", a[b[i]]);
			printf("%d = %d\n", a[b[n-1]]	, ans);
		}	
		return;
	}
	

	for(int i = pos; i < size; i++)
	{	
		b[k] = i;
		p(sum+a[b[k]], k+1, i+1);
				
	}

}
int main()
{
	p(0, 0, 0);	
	return 0;
}