Подорожуй з gofrie.com

У цей четвер на гуртку - Пошук

Гурток з програмування
Тема завтрашньої доповіді:
Пошук

Питання, що будуть розглянуті:
  • Алгоритм Карпа Рабіна
  • Алгоритм Бойєра — Мура
  • Алгоритм Кнута Моріса Пратта

Презентація та додаткові матеріали

13 березня 2014, 16:30
Аудиторія 1-331

Доповідатиме Василь Куцик

Дуже сподобалась задача.

Підшивка ім. kutsyk
Хто зробить задачу той молодець:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of «and» when writing out numbers is in compliance with British usage.

Хто не знає є такий крутий сервіс: projecteuler

Задача: Розв’язати рівняння f(x)=0 (метод дихотомії)

Вступна контрольна робота
Монотонна неперервна функція f(x) задана на відрізку [a,b], на кінцях якого вона приймає значення різних знаків. Розв’язати рівняння f(x)=0 на відрізку [a,b].

Задача: Ділення натуральних чисел з остачею

Вступна контрольна робота
Запрограмувати ділення натуральних чисел з остачею: m = qn+r; 0 \leq r < n.

Задача: Швидке піднесення до степеня

Вступна контрольна робота
Запрограмувати обчислення степеню з натуральним показником y = x^n, використавши істотно менше, ніж n кроків.

Вказівка: розглянути функцію z = yx^k, 0 \leq k \leq n.

Задача: Поліном Чебишева

Вступна контрольна робота
Написати функцію, що обчислює поліном Чебишева степеня n у точці x за наступною рекурентною формулою:
T_{0}(x) = 1; \;\;\; T_{1}(x) = x; \;\;\; T_{n}(x) = 2xT_{n-1}(x)-T_{n-2}(x); \;\;\; 2 \leq n \leq 10

Задача: НСД

Вступна контрольна робота
Написати функцію gcd(m, n) для обчислення найбільшого спільного дільника двох натуральних чисел (за алгоритмом Евкліда gcd(m,m) = m; gcd(m, m + n) = gcd(m,n)).
\forall m,n \in [1..1000000],\;\;\; m,n \in \mathbb{N}

Задача: y = sin(x)

Вступна контрольна робота
Необхідно реалізувати функцію mysin(x, eps), з заданною точністю eps (eps > 0), що розраховується за формулою:
S_n(x) = \sum\limits_{k=0}^n \frac{(-1)^k x^{2k+1}}{2k+1!}
\sin(x) = \lim_{n\to\infty}{S_n(x)} \;\;\;\; \ \;\;\;\; \forall x \in \mathbb{R}
Властивість:
\sin(x+2\pi k) = \sin(x) \;\;\;\; \forall x \in \mathbb{R} \;\;\;\; \forall k \in \mathbb{Z}

Задача: Сума

Вступна контрольна робота
Необхідно реалізувати функцію sum(x, n). Що розраховується за формулою:
S_n(x) = \sum\limits_{k=0}^n \frac{(-1)^k x^k}{k!} \;\;\;\; \forall n \geq 0 \;\;\;\; \forall x \in R
Приклади:
S_2(0) = 1
S_{10}(1) = 0.367879188713

Задача: Фібоначчі

Вступна контрольна робота
Напишіть програму обчислення послідовності Фібоначі.
f_0 = 0; f_1 = 1; f_n = f_{n-1} + f_{n-2}.

Задача: Факторіал

Вступна контрольна робота
Необхідно написати, функцію factorial, яка обчислює факторіал числа.