Книга "Если бы у Эйлера был компьютер. Решаем сложные и олимпиадные задачи"

[Valery]

Начало конца недели должно начинаться бурно - с решения задач на паскале, которые здесь:

Если бы у Эйлера был компьютер

Исходники здесь: _Projects.zip (290,6 КБ)

Я решал задачи для своего удовольствия, и вполне доволен, что выбрал для этого PascalABC.NET. В нём есть всё, про всё и для всего. Нужно только правильно его готовить, иначе программы получаются невкусные!

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

Изучайте паскаль и получайте настоящее, истинное удовольствие от программирования!

[Catcher]

@Valery По первой задаче, количество пятерок в разложении чисел от 1 до 1000 на простые множители.

begin writeln(1000 div 5 + 1000 div 25 + 1000 div 125 + 1000 div 625) end.

Одна строчка вместо 14. Выполняется моментально. Или если хочется убедиться, что это верно:

$ for i in {1..1000}; do factor "$i"; done | tr ' ' '\n' | grep -c '^5$'
249

Или если хочется расширяемости на произвольный диапазон:

i := 1;
n := 1000;
m := 0;
while i <= n do begin
	i := i * 5;
	m := m + n div i
end
writeln(m)

С рекурсией у тебя тут проблемы, она не хвостовая, а потому если список будет из пары-тройки тысяч или миллионов элементов, у тебя она сожрёт весь стек. Правильная рекурсия выглядит так:

$ cat ./sumlist.tcl
#!/usr/bin/env jimsh
proc sum {list sum} {
	if {![llength $list]} {
		return $sum
	} else {
		tailcall sum [lrange $list 0 end-1] $($sum+[lindex $list end])
	}
}
puts [sum {1 2 3 5 7 9} 0]
$ ./sumlist.tcl 
27

Заметь в чём отличие: вывод самой же функции sum является выводом её же на предыдущем шаге рекурсии, поэтому можно запустить её в том же стековом фрейме. На паскале тоже так можно, но оптимизация включается только на fpc -O3 или -O2, точно не помню

Вырезание квадратов из прямоугольника — это алгоритм Евклида.

Поскольку длина последовательности заранее неизвестна, то для её хранения разумно использовать список. В Турбопаскале такая структура данных отсутствует, поэтому элементы нужно хранить в массиве, длину которого следует знать заранее.

В смысле отсутствует?

Type
	PLinkedList=^TLinkedList;
	TLinkedList=record
		Number: integer;
		Next: PLinkedList;
	end;

А это что тогда?

А задача такая: подсчитать число разных прямоугольников в сетке 9 х 9 клеток.

Решение в книге неправильное, например для сетки 2×2 должен получиться ответ 6, а для 3×3 — 44. Программу лень писать.