прекалк

@diagon · Регистрация: 02.05.2010

Author24 — интернет-сервис помощи студентам

Доброго времени суток
Знаю, что есть задачи, которые можно решить только с помощью этого прекалка.
Но что это такое - найти не могу =(
Просьба дать линки на какую-нибудь литературу по этой теме, либо объяснить на примере.
Что он делает, примерно представляю - на олимпиадные задачи отводится определенное время, обычно 1 секунда. Иногда этого недостаточно, и в таких случаях, как я понял, пишут прекалк, т.е. на этапе компиляции вычисляют все возможные значения и затем тупо находят среди них нужный. А вот как это делают - без понятия, и нагуглить ничего толкового не получается.

@Deviaphan · 18.06.2011, 16:00

Вместо а = 5 + 7 пишешь а = 12. Это элементарный вариант прекалка.)
А вообще, скорее всего имеется ввиду замена "длительных" функций на предвычесленное значение. Например, создаётся таблица синусов угла и вместо вызова функции sin используется индексный доступ к массиву.

@diagon · 18.06.2011, 16:06 **[ТС]**

Хм... А как ее сделать на этапе компиляции
Насколько я понял, прекалком вы называете например такой код

C++

1 2	int x=sqrt(y); for (int i=0; i < x; ++i);

Но я нашел немного другое объяснение

имеется задача - найти факториал числа N... ограничения 0<N<100. Время 0.005 сек. Короче говоря, если делать в лоб, то по времени не пройдет. НО можно заранее подсчитать все факториалы чисел до 100, проициализировать массивчик этими значениями и уже выводить готовый ответ без подсчетов. Вот такой подход называется прекалк.. может у него есть другие названия, но я их не встречал

Сомневаюсь, что можно за 0.005 сек вычислить все факториалы до 100. Значит, вычисляются они на этапе компиляции. Как такое сделать?
Или это невозможно и я ошибаюсь?

@Deviaphan · 18.06.2011, 16:15

Сообщение от diagon

Насколько я понял

Не правильно понял.

Например, массив синусов, о котором я сказал выше:

C++

1
2
3

float sinus[360] = { 0, 0.017452406, 0.034899496, ... /*остальные синусы до 359 градусов*/};
//В коде, вместо sin(45) пишеш
float result = sinus[45];

Добавлено через 1 минуту

Сообщение от diagon

омневаюсь, что можно за 0.005 сек вычислить все факториалы до 100.

Сомневаюсь, что ты сможешь вычислить !100 не используя длинную арифметику.)

@diagon · 18.06.2011, 16:15 **[ТС]**

Да, спасибо, теперь дошло...

Сомневаюсь, что ты сможешь вычислить !100 не используя длинную арифметику.)

А почему бы ее не использовать?)
Есть готовый код для факториала даже.

Jupiter · 18.06.2011, 16:17

Сообщение от diagon

Сомневаюсь, что можно за 0.005 сек вычислить все факториалы до 100. Значит, вычисляются они на этапе компиляции.

метапрограммно

@diagon · 18.06.2011, 16:18 **[ТС]**

Сообщение от Maxwe11

метапрограммно

Хм... а поподробнее?
Где об этом можно почитать?

Jupiter · 18.06.2011, 16:22

примерчик в 3-м посте)
факториал в с++

@diagon · 18.06.2011, 16:35 **[ТС]**

Хм... Если бы я еще ООП в с++ знал...
Отложу пока до лучших времен, на олимпиадах за прекалк, который компилятор на час загрузит, и кастрировать могут =)
Всем спасибо.

@Deviaphan · 18.06.2011, 16:37

Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП?

@diagon · 18.06.2011, 16:40 **[ТС]**

Сообщение от Deviaphan

Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП?

Хм... тоже вариант.
Про массив я намотал на ус, не пользовался таким раньше, но нужно было именно вычисление на этапе компиляции.

silent_1991 · 18.06.2011, 16:44

diagon, а в факториале ООП причём? Шаблоны - обобщенное, а не объектно-ориентированное программирование.
Вот вам вариант без классов (если именно они вас смущают, хотя он абсолютно ничем не отличается от классов с публичными членами):

C++

#include <iostream>
 
template< int N >
struct Factorial
{
    static const long long n = N * Factorial< N - 1 >::n;
};
 
template< >
struct Factorial< 0 >
{
    static const long long n = 1;
};
 
int main()
{
    long long fact5 = Factorial< 5 >::n;
    long long fact8 = Factorial< 8 >::n;
 
    std::cout << fact5 << std::endl << fact8 << std::endl;;
        
    return 0;
}

@Deviaphan · 18.06.2011, 16:44

На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном.

@diagon · 18.06.2011, 16:47 **[ТС]**

Сообщение от silent_1991

diagon, а в факториале ООП причём? Шаблоны - обобщенное, а не объектно-ориентированное программирование.

Шаблоны в общих чертах знаю, а классы даже не начинал(там класс Factorial используется). Ну принципы ООП немного из java знаю, но оно там намного проще, чем в с++.

На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном.

Хм... А с вектором интов(в основном для длинной арифметики надо) как дело обстоит?

silent_1991 · 18.06.2011, 16:49

Сообщение от diagon

но оно там намного проще, чем в с++

о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы.

@diagon · 18.06.2011, 16:52 **[ТС]**

Сообщение от silent_1991

о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы.

Я про само ООП(тавтология получилась, ну да ладно)
Например, в java нету виртуальных функций, нету указателей и еще много всего, чего я не знаю=)
Просто в книге по java, которую я читаю, идет сравнение с++ с java, очень много возможностей с++ там просто вырезано.

@Deviaphan · 18.06.2011, 16:52

Сообщение от diagon

А с вектором интов

Точно помню, что задавался этим вопросом, искал, нашёл ответ. Но т.к. это было просто любопытство, то уже не помню ответа.)
Есть подозрение, что нельзя.)

silent_1991 · 18.06.2011, 16:54

diagon, виртуальные функции в Java есть, просто они там все виртуальные по умолчанию. Указатели с ООП ничего общего не имеют.

@diagon · 18.06.2011, 17:04 **[ТС]**

Не по теме:

Такое ощущение, что меня переманивают на темную сторону с++:D
Но в ближайшее время мне ничего, кроме процедурного программирования не понадобится, собственно и java я начал учить только из-за родной длинной арифметики=)
Лучше потрачу время на алгоритмы

Ок, спасибо, поковыряюсь с шаблонами.

silent_1991 · 18.06.2011, 20:16

Не по теме:

diagon, да нет, зачем своими руками клепать конкурентов? :D
На самом деле я просто уточнил некоторые моменты, о которых у вас сложилось несколько неверное представление))

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	18.06.2011, 16:44	13
	На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 16:47 [ТС]	14
	Сообщение от silent_1991 diagon, а в факториале ООП причём? Шаблоны - обобщенное, а не объектно-ориентированное программирование. Шаблоны в общих чертах знаю, а классы даже не начинал(там класс Factorial используется). Ну принципы ООП немного из java знаю, но оно там намного проще, чем в с++. На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном. Хм... А с вектором интов(в основном для длинной арифметики надо) как дело обстоит? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
		1
	прекалк 18.06.2011, 15:37. Показов 7606. Ответов 19 Метки прекалк (Все метки) Доброго времени суток Знаю, что есть задачи, которые можно решить только с помощью этого прекалка. Но что это такое - найти не могу =( Просьба дать линки на какую-нибудь литературу по этой теме, либо объяснить на примере. Что он делает, примерно представляю - на олимпиадные задачи отводится определенное время, обычно 1 секунда. Иногда этого недостаточно, и в таких случаях, как я понял, пишут прекалк, т.е. на этапе компиляции вычисляют все возможные значения и затем тупо находят среди них нужный. А вот как это делают - без понятия, и нагуглить ничего толкового не получается. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	18.06.2011, 16:00	2
	Вместо а = 5 + 7 пишешь а = 12. Это элементарный вариант прекалка.) А вообще, скорее всего имеется ввиду замена "длительных" функций на предвычесленное значение. Например, создаётся таблица синусов угла и вместо вызова функции sin используется индексный доступ к массиву. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 16:15 [ТС]	5
	Да, спасибо, теперь дошло... Сомневаюсь, что ты сможешь вычислить !100 не используя длинную арифметику.) А почему бы ее не использовать?) Есть готовый код для факториала даже. 0

Jupiter Каратель 6609 / 4028 / 401 Регистрация: 26.03.2010 Сообщений: 9,273 Записей в блоге: 1
	18.06.2011, 16:17	6
	Сообщение от diagon Сомневаюсь, что можно за 0.005 сек вычислить все факториалы до 100. Значит, вычисляются они на этапе компиляции. метапрограммно 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 16:18 [ТС]	7
	Сообщение от Maxwe11 метапрограммно Хм... а поподробнее? Где об этом можно почитать? 0

Jupiter Каратель 6609 / 4028 / 401 Регистрация: 26.03.2010 Сообщений: 9,273 Записей в блоге: 1
	18.06.2011, 16:22	8
	примерчик в 3-м посте) факториал в с++ 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 16:35 [ТС]	9
	Хм... Если бы я еще ООП в с++ знал... Отложу пока до лучших времен, на олимпиадах за прекалк, который компилятор на час загрузит, и кастрировать могут =) Всем спасибо. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	18.06.2011, 16:37	10
	Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 16:40 [ТС]	11
	Сообщение от Deviaphan Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП? Хм... тоже вариант. Про массив я намотал на ус, не пользовался таким раньше, но нужно было именно вычисление на этапе компиляции. 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.06.2011, 16:49	15
	Сообщение от diagon но оно там намного проще, чем в с++ о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 16:52 [ТС]	16
	Сообщение от silent_1991 о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы. Я про само ООП(тавтология получилась, ну да ладно) Например, в java нету виртуальных функций, нету указателей и еще много всего, чего я не знаю=) Просто в книге по java, которую я читаю, идет сравнение с++ с java, очень много возможностей с++ там просто вырезано. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	18.06.2011, 16:52	17
	Сообщение от diagon А с вектором интов Точно помню, что задавался этим вопросом, искал, нашёл ответ. Но т.к. это было просто любопытство, то уже не помню ответа.) Есть подозрение, что нельзя.) 1

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.06.2011, 16:54	18
	diagon, виртуальные функции в Java есть, просто они там все виртуальные по умолчанию. Указатели с ООП ничего общего не имеют. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.06.2011, 17:04 [ТС]	19
	Не по теме: Такое ощущение, что меня переманивают на темную сторону с++:D Но в ближайшее время мне ничего, кроме процедурного программирования не понадобится, собственно и java я начал учить только из-за родной длинной арифметики=) Лучше потрачу время на алгоритмы Ок, спасибо, поковыряюсь с шаблонами. 0

silent_1991
	18.06.2011, 20:16 прекалк #20
	Не по теме: diagon, да нет, зачем своими руками клепать конкурентов? :D На самом деле я просто уточнил некоторые моменты, о которых у вас сложилось несколько неверное представление)) 0