Создание рекурсивного алгоритма
условие задачи:
1) дан массив разных целых чисел<=>т.е. конечное множество целых чисел которые расположены в определённой последовательности. (например: A={5,3,11,2,8,6,15,4}, в массиве A , 5 расположен на 1_ой позиции, 11 на 3_ой позиции, 4 на 8_ой позиции)
2) величина массива=n (целое число), т.е. n - количество членов множества. (например: для A={5,3,11,2,8,6,15,4} , n=8)
3) дано целое число m.
цель задачи: создать рекурсивный алгоритм который бы выявлял или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к данному множеству, так что-бы сумма всех чисел вышеуказанной группы=m.
хочу привести свой алгоритм решения задачи который основан на принципе:
"для того что бы доказать что существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[1,...,i,...,n], так что-бы сумма всех чисел вышеуказанной группы=m - достаточно доказать, что существует элемент массива A[ i ],
такой что существует группа чисел, являющихся подмножеством к
A[ i+1,...,n ], сумма которых равна m - А[ i ]".
Условие задачи:
a) пусть будет дан массив разных целых чисел A[1,...,i,...,n],
b)дано целое число m.
precondition: алгоритм получает исходное число i=1, массив разных целых чисел A[i,...,n],целое число m.
postcondition: алгоритм выдаёт результат TRUE или FALSE.
Алгоритм:
1)найди или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[i+1,...,n], так что-бы сумма всех чисел вышеуказанной группы=m-A[ i ].
2)если условие1 TRUE, рекурсия останавливается и алгоритм выдаёт результат TRUE
в противном случае(т.е. если условие1 FALSE) :
если условие i < n TRUE - инкрементируй i на 1, (т.е. i = i + 1) и выполняй условие1,
в противном случае - если условие i < n FALSE (т.е. i =n ) - рекурсия останавливается и алгоритм выдаёт результат FALSE.
Казалось бы всё просто-если существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву А , так что-бы сумма всех чисел вышеуказанной группы=m, то алгоритм обязательно это выявит и выдаст результат TRUE - но вся проблема в том как заставить алгоритм "добросовестно" проверять условие1
1) дан массив разных целых чисел<=>т.е. конечное множество целых чисел которые расположены в определённой последовательности. (например: A={5,3,11,2,8,6,15,4}, в массиве A , 5 расположен на 1_ой позиции, 11 на 3_ой позиции, 4 на 8_ой позиции)
2) величина массива=n (целое число), т.е. n - количество членов множества. (например: для A={5,3,11,2,8,6,15,4} , n=8)
3) дано целое число m.
цель задачи: создать рекурсивный алгоритм который бы выявлял или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к данному множеству, так что-бы сумма всех чисел вышеуказанной группы=m.
хочу привести свой алгоритм решения задачи который основан на принципе:
"для того что бы доказать что существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[1,...,i,...,n], так что-бы сумма всех чисел вышеуказанной группы=m - достаточно доказать, что существует элемент массива A[ i ],
такой что существует группа чисел, являющихся подмножеством к
A[ i+1,...,n ], сумма которых равна m - А[ i ]".
Условие задачи:
a) пусть будет дан массив разных целых чисел A[1,...,i,...,n],
b)дано целое число m.
precondition: алгоритм получает исходное число i=1, массив разных целых чисел A[i,...,n],целое число m.
postcondition: алгоритм выдаёт результат TRUE или FALSE.
Алгоритм:
1)найди или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[i+1,...,n], так что-бы сумма всех чисел вышеуказанной группы=m-A[ i ].
2)если условие1 TRUE, рекурсия останавливается и алгоритм выдаёт результат TRUE
в противном случае(т.е. если условие1 FALSE) :
если условие i < n TRUE - инкрементируй i на 1, (т.е. i = i + 1) и выполняй условие1,
в противном случае - если условие i < n FALSE (т.е. i =n ) - рекурсия останавливается и алгоритм выдаёт результат FALSE.
Казалось бы всё просто-если существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву А , так что-бы сумма всех чисел вышеуказанной группы=m, то алгоритм обязательно это выявит и выдаст результат TRUE - но вся проблема в том как заставить алгоритм "добросовестно" проверять условие1
Цитата:
Originally posted by Bagira
условие задачи:
1) дан массив разных целых чисел<=>т.е. конечное множество целых чисел которые расположены в определённой последовательности. (например: A={5,3,11,2,8,6,15,4}, в массиве A , 5 расположен на 1_ой позиции, 11 на 3_ой позиции, 4 на 8_ой позиции)
2) величина массива=n (целое число), т.е. n - количество членов множества. (например: для A={5,3,11,2,8,6,15,4} , n=8)
3) дано целое число m.
цель задачи: создать рекурсивный алгоритм который бы выявлял или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к данному множеству, так что-бы сумма всех чисел вышеуказанной группы=m.
хочу привести свой алгоритм решения задачи который основан на принципе:
"для того что бы доказать что существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[1,...,i,...,n], так что-бы сумма всех чисел вышеуказанной группы=m - достаточно доказать, что существует элемент массива A[ i ],
такой что существует группа чисел, являющихся подмножеством к
A[ i+1,...,n ], сумма которых равна m - А[ i ]".
Условие задачи:
a) пусть будет дан массив разных целых чисел A[1,...,i,...,n],
b)дано целое число m.
precondition: алгоритм получает исходное число i=1, массив разных целых чисел A[i,...,n],целое число m.
postcondition: алгоритм выдаёт результат TRUE или FALSE.
Алгоритм:
1)найди или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[i+1,...,n], так что-бы сумма всех чисел вышеуказанной группы=m-A[ i ].
2)если условие1 TRUE, рекурсия останавливается и алгоритм выдаёт результат TRUE
в противном случае(т.е. если условие1 FALSE) :
если условие i < n TRUE - инкрементируй i на 1, (т.е. i = i + 1) и выполняй условие1,
в противном случае - если условие i < n FALSE (т.е. i =n ) - рекурсия останавливается и алгоритм выдаёт результат FALSE.
Казалось бы всё просто-если существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву А , так что-бы сумма всех чисел вышеуказанной группы=m, то алгоритм обязательно это выявит и выдаст результат TRUE - но вся проблема в том как заставить алгоритм "добросовестно" проверять условие1
условие задачи:
1) дан массив разных целых чисел<=>т.е. конечное множество целых чисел которые расположены в определённой последовательности. (например: A={5,3,11,2,8,6,15,4}, в массиве A , 5 расположен на 1_ой позиции, 11 на 3_ой позиции, 4 на 8_ой позиции)
2) величина массива=n (целое число), т.е. n - количество членов множества. (например: для A={5,3,11,2,8,6,15,4} , n=8)
3) дано целое число m.
цель задачи: создать рекурсивный алгоритм который бы выявлял или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к данному множеству, так что-бы сумма всех чисел вышеуказанной группы=m.
хочу привести свой алгоритм решения задачи который основан на принципе:
"для того что бы доказать что существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[1,...,i,...,n], так что-бы сумма всех чисел вышеуказанной группы=m - достаточно доказать, что существует элемент массива A[ i ],
такой что существует группа чисел, являющихся подмножеством к
A[ i+1,...,n ], сумма которых равна m - А[ i ]".
Условие задачи:
a) пусть будет дан массив разных целых чисел A[1,...,i,...,n],
b)дано целое число m.
precondition: алгоритм получает исходное число i=1, массив разных целых чисел A[i,...,n],целое число m.
postcondition: алгоритм выдаёт результат TRUE или FALSE.
Алгоритм:
1)найди или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[i+1,...,n], так что-бы сумма всех чисел вышеуказанной группы=m-A[ i ].
2)если условие1 TRUE, рекурсия останавливается и алгоритм выдаёт результат TRUE
в противном случае(т.е. если условие1 FALSE) :
если условие i < n TRUE - инкрементируй i на 1, (т.е. i = i + 1) и выполняй условие1,
в противном случае - если условие i < n FALSE (т.е. i =n ) - рекурсия останавливается и алгоритм выдаёт результат FALSE.
Казалось бы всё просто-если существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву А , так что-бы сумма всех чисел вышеуказанной группы=m, то алгоритм обязательно это выявит и выдаст результат TRUE - но вся проблема в том как заставить алгоритм "добросовестно" проверять условие1
По-моему проще всего сделать так:
function hello(z : integer);
var flag : boolean;
begin
m := z;
flag := false;
for i := 1 to n do
if a <= m then
begin
hello(m-a);
flag := true;
end
if not(flag) then
Result := false
else
Result := true;
end;
Тогда функция hello будет возвращать истина если такое подмножество есть.