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

Индийская легенда - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
pashokman
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 44
12.05.2011, 10:01     Индийская легенда #1
НАРОД ПОМОГИТЕ ПЛЗ! ПОДСКАЖИТЕ КАК ВЫВЕСТИ ОЧ БОЛЬШОЕ ЧИСЛО В ЭТОЙ ЗАДАЧЕ НАПРИМЕР ЕСЛИ ВЗЯТЬ 10 ячейку?

"О шахматной доске и зернах". Известная индийская легенда утверждает, что когда великий гроссмейстер выиграл у падишаха в награду он попросил положить на первую клетку шахматной доски 1 зерно, на вторую - 2, на третью - 4, на четвертую - 16 и т.д. Опишите программу, содержащую рекурсивную процедуру вычисления количества зерен на n-й ячейке шахматной доски.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "stdafx.h"
#include "conio.h"
 
int func(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 2;
 
    return func(n-1)*func(n-1);
}
 
int main()
{
    int N;
    scanf("%d",&N);
    printf("%d",func(N));
    getch();
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2011, 10:01     Индийская легенда
Посмотрите здесь:

Turbo Pascal Легенда о Иосифе Флавии
MS Excel Легенда о шахматах
Легенда диаграммы Turbo Pascal
C++ Builder БД DBChart. Легенда графика
Компонента MSChart: Легенда Visual Basic
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
12.05.2011, 10:34     Индийская легенда #2
использовать не int, а long double
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 10:44     Индийская легенда #3
Здесь длинная арифметика видимо, 2^N
pashokman
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 44
12.05.2011, 10:52  [ТС]     Индийская легенда #4
LineStown не работает даже если заменить на long double вот сам поробуй будет ли выводить число если ввести 10 ячейку!?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 11:58     Индийская легенда #5
Это же очень простая задача...
Хотя довольно интересная=)
Максимальное значение unsigned long long 18446744073709551615, при 64 ячейке вроде такой же результат получится.
а 10 ячейка - это всего-лишь 2055.
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
12.05.2011, 12:02     Индийская легенда #6
Цитата Сообщение от pashokman Посмотреть сообщение
на первую клетку шахматной доски 1 зерно, на вторую - 2, на третью - 4, на четвертую - 16 и т.д.
не, на четвертую надо 8, на пятую 16 ... такая легенда

Добавлено через 1 минуту
Цитата Сообщение от pashokman Посмотреть сообщение
return func(n-1)*func(n-1);
поэтому это надо заменить на
C++
1
return 2*func(n-1);
хотя, если речь о какой-то особой легенде, то действительно числа будут расти очень быстро)))

Добавлено через 28 секунд
Цитата Сообщение от diagon Посмотреть сообщение
10 ячейка - это всего-лишь 2055
512)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 12:05     Индийская легенда #7
Разве? Там же вроде сумму всех ячеек найти надо, а это (2^N+1)-1
А, пардон, тогда это очень простая задача.
2^63= 18446744073709551615
signed long long 9223372036854775807
Так что в unsigned int64
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
12.05.2011, 12:05     Индийская легенда #8
Максимальное число будет 2^63, так как всего 64 клетки у шахматной доски, но сказано что в первой клетке 1 мешок зерна, следовательно из этих соображений финальное число будет равно 2^63. Такое число можно записать в int64. int64 может сожержать число до диапозона 2*10^64.
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
12.05.2011, 12:08     Индийская легенда #9
Цитата Сообщение от diagon Посмотреть сообщение
Разве? Там же вроде сумму всех ячеек найти надо, а это (2^N+1)-1
Цитата Сообщение от pashokman Посмотреть сообщение
Опишите программу, содержащую рекурсивную процедуру вычисления количества зерен на n-й ячейке шахматной доски.
...........
vet
 Аватар для vet
175 / 175 / 13
Регистрация: 08.04.2009
Сообщений: 1,309
12.05.2011, 12:08     Индийская легенда #10
Цитата Сообщение от diagon Посмотреть сообщение
Максимальное значение unsigned long long 18446744073709551615, при 64 ячейке вроде такой же результат получится
2^64=18446744073709551616, так что unsigned long long не хватит =)
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
12.05.2011, 12:10     Индийская легенда #11
Цитата Сообщение от diagon Посмотреть сообщение
Максимальное значение unsigned long long 18446744073709551615, при 64 ячейке вроде такой же результат получится.
нет, только 2^63 поэтому войдет
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 12:11     Индийская легенда #12
Цитата Сообщение от vet Посмотреть сообщение
2^64=18446744073709551616, так что unsigned long long не хватит =)
64ую можно строчкой вывести, но вообще она всего на 1 больше максимального значения unsigned 64=)
pashokman
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 44
12.05.2011, 12:11  [ТС]     Индийская легенда #13
я вот про это и спрашиваю там получается надо суму найти! и получится очень большое число я уже перепробывал много типов и ничего не подходит
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
12.05.2011, 12:12     Индийская легенда #14
Цитата Сообщение от pashokman Посмотреть сообщение
там получается надо суму найти!
Цитата Сообщение от pashokman Посмотреть сообщение
Опишите программу, содержащую рекурсивную процедуру вычисления количества зерен на n-й ячейке шахматной доски.
Так сумму надо, или только количество зерен на n-ой ячейке???
Если сумму, то 2^n-1 где n-номер ячейки, для 64 это 2^64-1, влезет в unsigned long long)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 12:13     Индийская легенда #15
Цитата Сообщение от pashokman Посмотреть сообщение
я вот про это и спрашиваю там получается надо суму найти! и получится очень большое число я уже перепробывал много типов и ничего не подходит
Если сумму всех ячеек находить, то 64 выводится строкой, а 63 равна максимальному значению unsigned long long
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
12.05.2011, 12:14     Индийская легенда #16
Если сумму всех ячеек находить, то 64 выводится строкой, а 63 равна максимальному значению unsigned long long
Вот и решение =)
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
12.05.2011, 12:15     Индийская легенда #17
Цитата Сообщение от diagon Посмотреть сообщение
63 равна максимальному значению unsigned long long
неправда, возьми листочек, ручку и посчитай
pashokman
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 44
12.05.2011, 12:16  [ТС]     Индийская легенда #18
ой сори я уже сам запутался там надо вывести количество зерен на n-ячейке!
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
12.05.2011, 12:17     Индийская легенда #19
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "stdafx.h"
#include "conio.h"
 
unsigned long long func(int n)
{
    if (n == 1) return 1; 
    return 2*func(n-1);
}
 
int main()
{
    int N;
    scanf("%d",&N);
    printf("%d",func(N));
        getch();
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2011, 12:18     Индийская легенда
Еще ссылки по теме:

Легенда для карты C++ Qt
Легенда про try catch C#
Matlab Динамическая легенда в цикле

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 12:18     Индийская легенда #20
С листочком и ручкой долго однако считать придется...)
2^64-1=18446744073709551615
Правда тоже строчкой выводить придется, т.к. сначала получится число, которое больше insigned int 64, и после его декремента получится нужное.
К посту выше-в int не влезет.
Ну на одной ячейке неинтересно=)
P.S.я в си не очень разбираюсь, но спецификатор вывода на %I64 надо заменить если signed, как unsigned не знаю
Yandex
Объявления
12.05.2011, 12:18     Индийская легенда
Ответ Создать тему
Опции темы

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