Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Count
0 / 0 / 0
Регистрация: 06.11.2011
Сообщений: 24
#1

Функции. Рекурсия. - C++

29.11.2011, 08:45. Просмотров 609. Ответов 4
Метки нет (Все метки)

Пишем в Microsoft Visual Studio -> Win32 Console Application -> C++. С помощью Рекурсий.

Условие задачи :
Перемещение N дисков может быть легко представлено в терминах перемещения только N-1 диска (и, следовательно, рекурсивно):
1. Переместить N-1 дисков с колышка 1 на колышек 2, используя колышек 3 как место временного размещения.
2. Переместить последний диск ( наибольший ) с колышка 1 на колышек 3
3. Переместить N-1 дисков с колышка 2 на колышек 3, используя колышек 1 как место временного размещения.
Используйте рекурсивную функцию с четырьмя параметрами:
1. Количество дисков, которое должно быть перемещено.
2. Колышек, на который эти диски нанизаны первоначально.
3. Колышек, на который эта группа дисков должна быть перемещена.
4. Колышек, используемый как место временного размещения.
Ваша программа должна печатать четкие инструкции, что нужно делать для перемещения дисков с начального колышка на конечный. Например, чтобы передвинуть группу из трех дисков с колышка 1 на колышек 3, ваша программа должна напечатать следующую последовательность перемещений:
1->3 (это обозначает перенос диска с 1-го колышка на 3-ий)
1->2
3->2
1->3
2->1
2->3
1->3

На сколько я знаю это не много сложней чем ряд Фибоначчи, но как это "выразить" без понятия, очень надеюсь на вашу помощь.
(Кажется такую задачу, с помощью массивов решил всего один человек в мире, если у кого есть ссылка на более детальную информацию буду благодарен! )

Добавлено через 14 часов 23 минуты
Ряд Фибоначчи

C++
1
2
3
4
5
6
7
8
9
    int F (int n)
    {
        if(n<0)
    return 0;
    else if (n==0 || n==1)
        return n;
    else
        return F(n-1) + F(n-2);
    }

Что бы написать перемещение дисков нужно не много поменять ряд (Я так думаю)...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2011, 08:45     Функции. Рекурсия.
Посмотрите здесь:

Функции (рекурсия) C++
C++ Функции рекурсия
C++ Рекурсия, функции.
C++ Рекурсия функции. Сумма целых чисел n и m, в которой из арифметических операций используется только прибавление и вычисление единицы
C++ функции рекурсия (Введить первое, третье, пятое и т.д. с вивединих чисел. Завершальний ноль выводить не над)
Рекурсия, ряд Фибоначчи (определить количество рекурсивных вызовов функции) C++
Рекурсия: вычисление функции Аккермана C++
C++ рекурсия функции
Рекурсия. Найти значение функции через разложение в ряд Тейлора C++
C++ Вычисление значения функции, заданной рядом Тейлора (рекурсия)
Рекурсия для поиска вещественного корня функции f(x) на отрезке [a, b] C++
Функции. Рекурсия на примере Фибоначчи C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Count
0 / 0 / 0
Регистрация: 06.11.2011
Сообщений: 24
30.11.2011, 08:55  [ТС]     Функции. Рекурсия. #2
Не кто не знает?(
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
30.11.2011, 11:16     Функции. Рекурсия. #3
Count, поищи в инете ханойские башни - очень известная задача, во всех учебниках про рекурсивные функции она описана.
dickivs
46 / 46 / 6
Регистрация: 25.11.2011
Сообщений: 270
Завершенные тесты: 1
30.11.2011, 14:08     Функции. Рекурсия. #4
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
#include <iostream>
using namespace std;
 
/* Максимальное число колец */
int st[4][64];   /* 1,2,3 - стержни */
int nr[4]; /* Число колец на стержнях */
int nmoves; /* Число перемещений */
/* ---------------------------------------------- 
Печать текущего расположения колец на стержнях 
---------------------------------------------- */
void print_st()
 
{
int i, j;
for(i = 1; i <= 3; i++) {
cout<<endl;
cout<<("| ");
 
for(j = 0; j < nr[i]; j++) cout<<st[i][j];
 
}
cout<<endl;
}
/* ------------------------------------
Установка начального положения колец 
/* ------------------------------------ */
void init(int nrings)
{
for(nr[1] = 0; nrings > 0; nr[1]++,nrings--)
st[1][nr[1]] = nrings;
/* Нанизали кольца на 1-й стержень */
nr[2] = nr[3] = 0;
/* Два других стержня пусты */
nmoves = 0;
print_st();
}
/* ----------------------------- 
Функция переносит одно кольцо 
со стержня n1 на стержень n2 
----------------------------- */
void move1(int n1, int n2)
{
st[n2][nr[n2]++] = st[n1][--nr[n1]];
//  sleep(1); /* Пауза в 1 секунду */
print_st(); /* Печать текущей позиции */
nmoves++;
}
/* ------------------------------------------------- 
Функция hanoi перемещает верхние nrings колец 
со стержня i1 на стержень i3, используя стержень 
i2 в качестве промежуточного. 1 <= i1,i2,i3 <= 3. 
------------------------------------------------- */
void hanoi(int nrings, int i1, int i2, int i3)
{
if(nrings == 1)
move1(i1, i3);
else {
hanoi(nrings-1, i1, i3, i2);
move1(i1, i3);
hanoi(nrings-1, i2, i1, i3);
}
}
void main()
{
int nrings;
cout<<"Number of rings: ";
cin>>nrings;
init(nrings);
hanoi(nrings, 1, 2, 3);
cout<<"End\n";
cout<<"Count of moves: "<<nmoves<<endl; 
 
}
Count
0 / 0 / 0
Регистрация: 06.11.2011
Сообщений: 24
30.11.2011, 16:43  [ТС]     Функции. Рекурсия. #5
Большое спасибо всем за помощь!
Yandex
Объявления
30.11.2011, 16:43     Функции. Рекурсия.
Ответ Создать тему
Опции темы

Текущее время: 18:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru