Консультация № 51954
12.08.2006, 20:20
0.00 руб.
0 6 1
Задачка из классики.
1. Есть массив чисел длиной от 1 до 25 элементов формируемый динамически. Элементы массива - случайные числа в диапазоне от 0 до 100.
2. Переменная - число, тоже получаем случайно.
Все числа в диапазоне от 0 до 100.
Нужно максимально быстро найти все комбинации элементов массива(1), суммируя которые получаем заданное число(2).

Помогите, алгоритмом, плз, а то голова пухнет ночами сидеть.

Обсуждение

Неизвестный
12.08.2006, 20:45
общий
А Вам нужен "примитивный" полный перебор или максимально оптимизированный вариант?
Неизвестный
12.08.2006, 20:47
общий
Вы какой язык программирования предпочитаете?
Неизвестный
12.08.2006, 20:59
общий
это ответ
Здравствуйте, Иваненко Виктор Анатольевич!

Самое простое, что пришло в голову (на C++):

Приложение:
int rand_numbers[25]; // массив случайных чиселint rand_num; // количество чисел в этом массивеint found[25]; // массив для хранения "разложения"// рекурсивная процедура нахождения возможных сумм для числа Nvoid FindSum(int N,int pos=0,int fpos=0){ if(N==0) {//найдена сумма, выводим на экран printf("%d",found[0]); for(int i=1;i<fpos;i++) printf("+%d",found[i]); printf("\n"); } else if(pos<25-1) { FindSumRecursive(N,pos+1); found[fpos]=rand_numbers[pos]; FindSumRecursive(N-rand_numbers[pos],pos+1,fpos+1); }}
Неизвестный
12.08.2006, 21:01
общий
FindSumRecursive ЗАМЕНИТЬ НА FindSum!!! (опечатка)
Неизвестный
13.08.2006, 13:23
общий
Эту задачу я хочу решить на ActionScript 2.0 (Flash).Ещё руки не дошли рассмотреть ваше решение внимательнее. С оценкой попозже.
Неизвестный
13.08.2006, 13:26
общий
Если, например, в массиве есть числа 1, 5, 1. нужная сумма при этом - 7. Ваша программа справится с такой задачей?Сорри, торможу. Ещё не отоспался после двух суток непрерывного бодрствования.
Форма ответа