Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Michail97
93 / 40 / 23
Регистрация: 18.09.2016
Сообщений: 372
1

Рекурсивные функции

02.04.2017, 15:59. Просмотров 279. Ответов 0
Метки нет (Все метки)

Задан такой пример кода с комментариями. Очень хотелось бы разобраться.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*Задача 6.5: Дан ряд целых положительных чисел (максимально 30) и еще одно число. Расставить знаки операций сложение и вычитание между этими числами так, что бы получить верное равенство. Пример:
Дано:      1 2 3 4 5 6 7 8 9   13
Результат: 1+2+3+4+5+6-7+8-9 = 13
В программе вводится: количество чисел в ряду, сам ряд чисел и правая часть. При реализации использовать рекурсию.
Программа для задачи*/
#include <stdio.h>    //Библиотека функций ввода и вывода
#include <stdlib.h>   //Библиотека стандартных функций
#include <locale.h>
typedef struct{       //Структура для хранения всех данных
  int num;            //Количество чисел
  int *list;          //Указатель на массив чисел
  int summa;          //Сумма, которую надо получить
  unsigned operations;//Расстановка операций
} DATA;
/* --------------------------------------------------------
В поле operations находится комбинация операций: бит равный
единице - плюс, бит равный нулю - минус. Например:
Число:    10101100
Операции: +-+-++--
Порядок - с младших разрядов
-------------------------------------------------------- */
/* ---------- Функция вычисления выражения ------------- */
int Calc(DATA *);
/* ----------- Функция установки операции -------------- */
int Next(DATA *,int);
/* ---------- Главная функция программы: main ---------- */
int main(int argc, char *argv[])
{
  setlocale(LC_ALL, "");
  //Объявление переменой для хранения всех данных
  DATA data = {0,NULL,0,0};
  //Приглашение к вводу количества чисел и правой части
  printf("Введите количество чисел и результат: ");
  //Ввод количества чисел и правой части
  scanf("%d %d",&data.num,&data.summa);
  //Выделение памяти под список чисел
  data.list = (int *)calloc(data.num,sizeof(int));
  //Проверка выделения: если не выделилась - выход
  if(!data.list) {puts("Мало памяти!"); return 0;}
  //Приглашение к вводу чисел
  printf("Введите числа: ");
  //Ввод чисел
  int i; // переменная для счётчиков
  for( i=0;i<data.num;i++) scanf("%d",&data.list[i]);
  //Вызов функции для поиска комбинации операций
  if(Next(&data,0)){  //Если комбинация найдена
    //Вывод полученного выражения на экран
    unsigned operations = data.operations;
    //Цикл по всем действиям (количество чисел минус один)
    for( i=0;i<data.num-1;i++){
      //Вывод i-го числа и i-ой операции (+ или -)
      printf("%d%c",data.list[i],((operations%2)?'+':'-'));
      operations >>= 1;
    }
    //Вывод последнего числа
    printf("%d=%d\n",data.list[data.num-1],data.summa);
  }else puts("Не найдено!"); //Если комбинация не найдена
  free(data.list);  //Освобождение выделенной памяти
  return 0;
}
 
/* --------------------------------------------------------
Функция   проверяет:  совпадает ли результат вычисления
выражения  с  комбинацией  операций,  заданной  в  поле
operations структуры  с  целевым значением  (поле summa)
Если совпадает, то функция возвращает 1, если нет - 0
-------------------------------------------------------- */
int Calc(DATA *data)
{
    int i;
  //Переменная для вычисления суммы, сразу присваиваем
  int summa = data->list[0];  //первое число из списка
  //Сохраняем в локальной переменной комбинацию операций
  unsigned operations = data->operations;
  //Цикл по количеству операций
  for( i=1;i<data->num;i++){
    //Если операция: плюс, то суммируем с суммой
    if(operations % 2) summa += data->list[i];
      //если минус, то вычитаем из суммы
      else summa -= data->list[i];
    //Сдвигаем комбинацию операций вправо, удаляя тем самым
    operations >>= 1;  //вычисленную операцию
  }
  //Если суммы совпали, то возвращаем - единицу
  if(summa == data->summa) return 1;
  return 0;  //В противном случае - ноль
}
/* --------------------------------------------------------
Параметры функции:
  data - указатель на структуру с данными программы
  step - номер операции, которую определяем
Функция осуществляет определение операции в комбинации.
-------------------------------------------------------- */
int Next(DATA *data, int step)
{
  //Условие выхода из рекурсии: все операции определены
  //Проверяем истинность выражения и вовзращаем результат
  if(step == data->num-1) return Calc(data);
  //Устанавливаем текущую операцию: плюс
  data->operations |= (1 << step);
  //Рекурсивно  вызываем  для следующей операции,
  //если  результат - 1,  то  комбинация  найдена
  if(Next(data,step+1)) return 1;  //возвращаем 1
  //Устанавливаем текущую операцию: минус
  data->operations ^= (1 << step);
  //Рекурсивно  вызываем  для следующей операции,
  //если  результат - 1,  то  комбинация  найдена
  if(Next(data,step+1)) return 1;  //возвращаем 1
  return 0; //Если комбинация не найдена - возвращаем 0
}
В майне после введения в массив мы задаём нужную комбинацию двоичного представления, после которую, опираясь на младший разряд, ставим знак после числа. После каждого знака сдвигаем двоичное представление на один разряд вправо. Новым младшим разрядом становится предыдущее предшествующее число для изначально двоичного представления. Это понятно.
А вот как это двоичное представление формируется я не понимаю.
То есть 2 последние функции - calc и Next.
Если смотреть на первый вызов функции next, то в поле operations заносится значение 1(0|(1<<0)(наще двоичное представление для определение знака). А дальше по рекурсии я не понимаю, как определяется знак. Функция calc на самом деле понятна, она складывает отнимает в зависимости от числа на конце . Ведь если в двоичном представлении на конце ноль, то это число чётное и не имеет остатка, в противном наоборот.
Объясните, как работает рекурсия в функции NEXT, только начал строить рекурсивные функции и не совсем понимаю их организацию.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.04.2017, 15:59
Ответы с готовыми решениями:

Преобразовать функции в рекурсивные
Привет, нужна ваша помощь очень срочно, вопрос зачета и не зачета. Нужно изменить программу, так...

Как работают рекурсивные функции?
Всем привет! Ни как не могу понять как работают рекурсивные функции. а именно в каком месте...

Рекурсивные функции. Найдите n-ый член последовательности
Определите закономерность формирования членов последовательности. Найдите n-ый член...

Рекурсивные и не рекурсивные функции (вычисление суммы всех натуральных чисел от 1 до n)
Всем привет. Заранее извиняюсь за мб глупые вопросы и навязчивость. Но у меня есть одна просьба. ...

Рекурсивные функции, функции высшего порядка, преобразование императивных программ в функциональные
Простые рекурсивные функции для обработки списков: А) (ATOM-LIST x) проверяет, является ли х ...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.04.2017, 15:59

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Рекурсивные функции
Привет всем участникам форума! Помогите, пожалуйста, с решение следующей задачи: Описать...

Рекурсивные функции
Помогите пожалуйста с написание программы к двум задачкам: 1. Определить рекурсивную функцию,...

Рекурсивные функции
Функция twopow n, которая вычисляет 2n, исходя из следующих соображений. Пусть необходимо возвести...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.