int n = 5;
int w[] = {9,13,15,17,20,21};
int r[] = {0,0,0,0,0,0};
int s = 137;
bool recur(int j, int s) // j = n, n-1 ... 0
{
if(s % w[j] == 0)
{
r[j] = s/w[j];
return true;
}
else if (j == 0)
{
return false;
}
else
{
int k = s/w[j];
for(int i=k; i>=0; i--)
{
if( recur(j-1, s-w[j]*i) )
{
r[j] = i;
return true;
}
}
return false;
}
}
int main(int argc, char* argv[])
{
printf("n = %d\n\n", n);
for(int i = 0; i<=n; i++)
{
printf("w%d = %d ", i, w);
}
printf("\n\ns = %d\n\n", s);
if( recur( n, s ) )
{
int result = 0;
for(int i = 0; i<=n; i++)
{
if(i > 0) printf(" + ");
printf("%d*%d", w, r);
result += w*r;
}
printf(" = %d", result);
if(result == s) printf(" confirmed");
}
else
{
printf("No solution!");
}
getchar();
return 0;
}
Нужна помощь в создании рекурсивной подпрограммы
Здравствуйте, помогите пожалуйста разработать рекурсивный алгоритм, написать реализующую его рекурсивную подпрограмму в Builder C++ 6 в консольном приложении. Задание такое:
Имеются гири весом W[SIZE=1]0[/SIZE]<W[SIZE=1]1[/SIZE]<…<W[SIZE=1]n[/SIZE] Гирь каждого веса – любое достаточное количество. Найти хотя бы один набор гирь, в сумме дающих заданное с клавиатуры число.
Например, для гирь 2 < 3 < 5 и заданного числа 6, таким решением будет сумма 3 + 3 (или 2 + 2 + 2). :confused: :confused: :confused:
Мне очень нужна помощь просто у нас преподаватекль уехал а толком никто обьяснить материал не может вот и выкручиваемся студенты как можем [[COLOR=darkorange]Помогите мне[/COLOR]]
Имеются гири весом W[SIZE=1]0[/SIZE]<W[SIZE=1]1[/SIZE]<…<W[SIZE=1]n[/SIZE] Гирь каждого веса – любое достаточное количество. Найти хотя бы один набор гирь, в сумме дающих заданное с клавиатуры число.
Например, для гирь 2 < 3 < 5 и заданного числа 6, таким решением будет сумма 3 + 3 (или 2 + 2 + 2). :confused: :confused: :confused:
Мне очень нужна помощь просто у нас преподаватекль уехал а толком никто обьяснить материал не может вот и выкручиваемся студенты как можем [[COLOR=darkorange]Помогите мне[/COLOR]]
За оптимальность не ручаюсь, но работает вроде правильно:
Ой, забыла, что там число должно с клавиатуры вводиться! :eek:
Ну, сам исправишь, если понадобится :)
Код:
Ой, забыла, что там число должно с клавиатуры вводиться! :eek:
Ну, сам исправишь, если понадобится :)
Цитата: Sara
Ой, забыла, что там число должно с клавиатуры вводиться! :eek:
Ну, сам исправишь, если понадобится :)
Ну, сам исправишь, если понадобится :)
*************************************************
[FONT="Comic Sans MS"]Sara[/FONT] спасибо огромное за то, что выручили меня!
Я конечно сам подкорректирую программу чтоб число с клавы вводилось, это и не так собственно сложно будет сделать
/*Я очень вам благодарен*/:)
*************************************************
Здравствуйте! Вот я взялся за корректировку программы...ну хотел сделать чтобы пользователь все значения вводил с клавиатуры...но у меня не получилось...программа не выдает ответ [[COLOR="DarkOrange"]Помогите[/COLOR]]:confused:
У меня еще одна проблемка я не понимаю что значит в коде такие строчки как ("%d*%d"(Какая главная цель в этом случае указателя ?), s % w[j]) я этих действий ещё не знаю... [подскажите]
Код:
//--------------------------------------------------
#include <vcl.h>
#include <stdio.h>
char* Rus(const char* text);
int n = 5;
int w[] = {0,0,0,0,0,0};
int rkol[] = {0,0,0,0,0,0};
int s;
bool recur(int j, int s) /* j = n, n-1 ... 0 */
{
if(s % w[j]==0)
{
rkol[j] = s/w[j];
return true;
}
else if (j == 0)
{
return false;
}
else
{
int k = s/w[j];
for(int i=k-1; i>=0; i--)
{
if( recur(j-1, s-w[j]*i) )
{
rkol[j] = i;
return true;
}
}
return false;
}
}
//**************************************************
int main(int argc, char* argv[])
{
printf(Rus("\nКоличество гирь всего: "));
scanf("%d",&n);
printf(Rus("\nОбщий вес всех гирь: "));
scanf("%d",&s);
printf(Rus("\nВведите размерность гирь: "));
for(int i = 0; i<n; i++)
{
scanf("%d",&w);
}
printf("\nn= %d\n\n", n);
for(int i = 0; i<=n; i++)
{
printf("w%d = %d ", i, w);
}
printf("\n\ns = %d\n\n", s) ;
//**************************************************
if( recur( n,s ))
{
int result = 0;
for(int i = 0; i<=n; i++)
{
if(i > 0) printf(" + ");
printf("%d*%d", w, rkol);
result += w*rkol;
}
printf(" = %d", result);
if(result == s) printf(Rus("\Итоговый результат"));
}
else
{
printf(Rus("\nУ нас нет необходимых гирь для вывода!"));
}
getchar();
return 0;
}
//перевод русских букв в кодировку DOS
char bufRus[256];
char* Rus(const char* text)
{
CharToOem(text, bufRus);
return bufRus;
}
//--------------------------------------------------
#include <vcl.h>
#include <stdio.h>
char* Rus(const char* text);
int n = 5;
int w[] = {0,0,0,0,0,0};
int rkol[] = {0,0,0,0,0,0};
int s;
bool recur(int j, int s) /* j = n, n-1 ... 0 */
{
if(s % w[j]==0)
{
rkol[j] = s/w[j];
return true;
}
else if (j == 0)
{
return false;
}
else
{
int k = s/w[j];
for(int i=k-1; i>=0; i--)
{
if( recur(j-1, s-w[j]*i) )
{
rkol[j] = i;
return true;
}
}
return false;
}
}
//**************************************************
int main(int argc, char* argv[])
{
printf(Rus("\nКоличество гирь всего: "));
scanf("%d",&n);
printf(Rus("\nОбщий вес всех гирь: "));
scanf("%d",&s);
printf(Rus("\nВведите размерность гирь: "));
for(int i = 0; i<n; i++)
{
scanf("%d",&w);
}
printf("\nn= %d\n\n", n);
for(int i = 0; i<=n; i++)
{
printf("w%d = %d ", i, w);
}
printf("\n\ns = %d\n\n", s) ;
//**************************************************
if( recur( n,s ))
{
int result = 0;
for(int i = 0; i<=n; i++)
{
if(i > 0) printf(" + ");
printf("%d*%d", w, rkol);
result += w*rkol;
}
printf(" = %d", result);
if(result == s) printf(Rus("\Итоговый результат"));
}
else
{
printf(Rus("\nУ нас нет необходимых гирь для вывода!"));
}
getchar();
return 0;
}
//перевод русских букв в кодировку DOS
char bufRus[256];
char* Rus(const char* text)
{
CharToOem(text, bufRus);
return bufRus;
}
//--------------------------------------------------
У меня еще одна проблемка я не понимаю что значит в коде такие строчки как ("%d*%d"(Какая главная цель в этом случае указателя ?), s % w[j]) я этих действий ещё не знаю... [подскажите]
2 Krazist:
выводит на экран значение элемента w, символ '*' и значение элемента rkol.
я делаю вывод, что ты вообще не понял условия задачи. О чем можно говорить дальше?
Цитата:
что значит в коде такие строчки как ("%d*%d"(Какая главная цель в этом случае указателя ?)
Указатели тут ни при чем. Строчка
Код:
printf("%d*%d", w, rkol);
выводит на экран значение элемента w, символ '*' и значение элемента rkol.
Цитата:
s % w[j]) я этих действий ещё не знаю
s % w[j] - остаток от деления s на w[j].
Теперь по поводу твоей программы. Вот из этих строк
Код:
printf(Rus("\nКоличество гирь всего: "));
scanf("%d",&n);
printf(Rus("\nОбщий вес всех гирь: "));
scanf("%d",&s);
scanf("%d",&n);
printf(Rus("\nОбщий вес всех гирь: "));
scanf("%d",&s);
я делаю вывод, что ты вообще не понял условия задачи. О чем можно говорить дальше?
Код:
printf(Rus("\nКоличество гирь всего: "));
scanf("%d",&n);
printf(Rus("\nОбщий вес всех гирь: "));
scanf("%d",&s);
scanf("%d",&n);
printf(Rus("\nОбщий вес всех гирь: "));
scanf("%d",&s);
Я вставлял эти строчки чтоб значения с клавы вводились, но не получилось и попросил помощи...
Условие задачи я понял и хорошо представляю поставленную цель. Но я вас совсем не хотел обидеть...
to Krazist:
1. По условиям задачи веса W0<W1<…<Wn пронумерованы от 0 до n, т.е. массивы w[] и rkol[] имеют размерность n+1. А у тебя в этом цикле вводится только n элементов:
Последний элемент w[n] остается нулевым, из-за чего в функции recur происходит деление на 0.
2. Не знаю, ошибка ли это или так задумано, но если юзер введет с клавиатуры n > 5, твоя программа работать не будет. Чтобы она работала для любых n, надо использовать динамическое выделение памяти.
1. По условиям задачи веса W0<W1<…<Wn пронумерованы от 0 до n, т.е. массивы w[] и rkol[] имеют размерность n+1. А у тебя в этом цикле вводится только n элементов:
Код:
for(int i = 0; i<n; i++)
{
scanf("%d",&w);
}
{
scanf("%d",&w);
}
Последний элемент w[n] остается нулевым, из-за чего в функции recur происходит деление на 0.
2. Не знаю, ошибка ли это или так задумано, но если юзер введет с клавиатуры n > 5, твоя программа работать не будет. Чтобы она работала для любых n, надо использовать динамическое выделение памяти.
Да действительно чтобы она работала для любых значений n нужно использовать динамическое выделение памяти. Ну вот например программа в которой память под массив выделяется динамически.
В программе функция malloc делает запрос к ядру ОС по выделению заданного количества байт.
Единственный аргумент этой функции это число байт, которое нам нужно. В результате функция возвращает указатель на начало выделенной памяти. Всю память, которая была выделена с помощью функции malloc, нужно освободить с помощью функции free как и указано в проге.
Аргумент функции free это указатель на начало выделенной когда-то памяти.
<-Я понял как это сделать, и надеюсь прога будет корректно работать->
Код:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define N 1000
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, i;
int *a;
scanf("%d", &n);
a = (int*) malloc(sizeof(int)*n);
for(i = 0 ; i < n; i++) {
scanf("%d", &a);
}
qsort(a, n, sizeof(int), cmp );
for(i = 0 ; i < n; i++) {
printf("%d ", a);
}
free(a);
return 0;
}
#include <stdlib.h>
#include <malloc.h>
#define N 1000
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, i;
int *a;
scanf("%d", &n);
a = (int*) malloc(sizeof(int)*n);
for(i = 0 ; i < n; i++) {
scanf("%d", &a);
}
qsort(a, n, sizeof(int), cmp );
for(i = 0 ; i < n; i++) {
printf("%d ", a);
}
free(a);
return 0;
}
В программе функция malloc делает запрос к ядру ОС по выделению заданного количества байт.
Единственный аргумент этой функции это число байт, которое нам нужно. В результате функция возвращает указатель на начало выделенной памяти. Всю память, которая была выделена с помощью функции malloc, нужно освободить с помощью функции free как и указано в проге.
Аргумент функции free это указатель на начало выделенной когда-то памяти.
<-Я понял как это сделать, и надеюсь прога будет корректно работать->