Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача на количетсво вариантов заполнение площади

Автор: Nodl 16.09.2006 1:12

Условия:
Есть плитки размером 1х1 и 1х2. сколько вариантов заполнение ими площади размерами 2хN? Ограничения на кол-ство плиток нет, плитки 1х2 используються только 1х2(горизонтально), но не 2х1.
Прошу помочь

Автор: virt 16.09.2006 2:23

так как плитки 2х1 не используются ,то количество вариантов заполнения площади(2хn) это количество вариантов заполнения площади(1хn) возведенное в квадрат. А для заполнения 1хn количество вариантов это число фибоначи с номером n. Общая формула :: F(n) = F(n - 1) + F(n - 2). Например для n = 1 ответ 1 ,n = 2 ответ 2 ,n = 3 ответ 3 ...,n = 7 ответ 21.

volvo по моему и код рабочий приводил ,поиском по форуму найди.

Автор: Гость 18.09.2006 21:57

о спасибо большое! ну у меня такой вот простенкий алгоритмик вышел:
a:=1; b:=1; c:=0;
for i:=1 to n-1 do begin c:=a+b; a:=b; b:=c; end;
if n=1 then ans:=sqr(b) else ans:=sqr©;

если можно написать по лучче то скажите как плз. А то я учусь, пишу как удобно и не знаю стандартов. Еще раз спасибо

Автор: Nodl 18.09.2006 21:59

Автор: volvo 18.09.2006 22:16

Какие значения может принимать N? Если больше 47, то твой алгоритм начнет выдавать неверные результаты: LongInt при N > 47 переполняется... Придется задействовать длинную арифметику...

Автор: Nodl 18.09.2006 22:22

Не у меня N от 1 до 1000. Но даже если я напишу с Божьей помощю длинную арифметику ( с ней у меня всегда проблемы потому что проблемы с динамикой ) то у меня жесткое ограничение по времени. И вообще по тем тестам что я сдаю там N принимает не большие значение.