Форум «Всё о Паскале» _ Математика _ Последние цифры суммы
Автор: Анна М. 29.04.2006 22:22
Есть задача:
Цитата
Выражение 1^1+2^2+3^3+...+10^10=10405071317. Требуется найти последние 10 цифр выражения 1^1+2^2+3^3+...+1000^1000.
Решить задачу я смогу, я уверена.)) Однако подскажите принцип решения, за что браться и с чего начинать? А то до самой всё никак не доходит. Заранее благодарю.
Автор: Анна М. 1.05.2006 2:00
Также можно привести реализацию (частичную или полную) этой задачи на языках программирования, таких как Pascal.
Автор: Zxzc 1.05.2006 3:58
Я думаю дело в отбрасывании старших цифр, которые не влияют на значение младших. Например, пусть не 10 последних, а 3: 999 * 999 ________ 8991 8991 8991 (Перепиши это в столбик со смещением, а то с выравниванием напряги . Красным цветом - то, что влияет, черное - отбрасываем. При программировании надо будет взять за основу, что 10 цифр не уместятся в переменной(10 может и уместятся, но где 10 там и 11 ), а значит придется брать массив.
Автор: lapp 1.05.2006 19:11
Цитата(Анна М. @ 30.04.2006 22:00)
Также можно привести реализацию (частичную или полную) этой задачи на языках программирования, таких как Pascal.
Очень существенное добавление! Хорошо было бы его сделать своевременно.. Я уже поломал себе голову.. Конечно, это не решает всего. Но все же направление мысли корректируется.
Автор: Zxzc 2.05.2006 0:16
Я не смог придумать никакой особой формулы вычисления этой последовательности. А посредством циклов эта задача довольно просто решается.
Автор: volvo 2.05.2006 0:20
Цитата
А посредством циклов эта задача довольно просто решается.
Правда? Тогда приведи решение...
Автор: Malice 2.05.2006 3:42
Цитата(volvo @ 1.05.2006 20:20)
Правда? Тогда приведи решение...
У меня получилось "9110846700" - циклами, стандартными типами, пока приводить не буду
Автор: volvo 2.05.2006 3:48
Malice, ты меня извини, но у меня получилось что последние 19 цифр искомого числа равны 4348127819110846700 ВООБЩЕ без циклов. Простым поиском в Google.com ...
Результат - не проблема. Важно решение...
Автор: Malice 2.05.2006 22:54
Цитата(volvo @ 1.05.2006 23:48)
Malice, ты меня извини, но у меня получилось что последние 19 цифр искомого числа равны 4348127819110846700 ВООБЩЕ без циклов. Простым поиском в Google.com ...
Хитрый ты. Я не стал выкладывать - думал кто еще выскажется, а так вот:
uses crt; const mx=1.0E+16; var l,z:extended; i,j:integer; begin l:=0; for i:=1 to 1000 do begin z:=1; for j:=1 to i do begin z:=z*i; z:=z-trunc(z/mx)*mx; end; l:=l+z;l:=l-trunc(l/mx)*mx; end; writeln (l:0:0); readln; end.
Максимум 16 цифр таким способом получается, дальше точности не хватает..
Автор: zZz 2.05.2006 23:51
а я вот чего придумал... только вот компилировать прога всё это дело упорно отказывается, а MOD убирать нельзя, иначе переполнение пойдет... пробовал применять extended для описания переменных, так он(паскаль) у меня даже с таким типом не знаком, пришел к выводу, что мой паскаль - полный отстой... ну все же принцип таков, может у кого при небольшой редакции пойдет...
Цитата
var x,a,i,s:integer; begin s:=0; for x:=1 to 1000 do begin a:=1; for i:=1 to x do a:=((a*x) mod 10000000000); s:=((s+a) mod 10000000000); end; write(s); end.
Автор: volvo 7.05.2006 18:24
Цитата
может у кого при небольшой редакции пойдет...
zZz - не пойдет... Для 10 чисел отработает, и выдаст правильный результат. Для 1000 будет работать, но результат выдаст неверный...
Автор: zZz 7.05.2006 20:38
а почему не пойдет?, я так понимаю что проблема не в моей логике, а в особенности счисления компьютера, которой, я, к своему сожалению, не знаю... так что интересно было бы разобраться с причиной сего феномена
Автор: volvo 7.05.2006 21:11
Цитата(zZz @ 7.05.2006 16:38)
я так понимаю что проблема не в моей логике, а в особенности счисления компьютера
Емкости целочисленных типов Турбо Паскаля не хватает... Если делать вот так (компилятор - FPC):
var a, s: qword; { может принимать значения 0 .. 18446744073709551615 } x, i: integer;
begin s := 0; for x := 1 to 1000 do begin a := 1; for i := 1 to x do a := (a*x) mod 10000000000; s := (s+a) mod 10000000000; end; writeln(s); end.
, то все прекрасно считается...
Автор: zZz 7.05.2006 21:25
ну я вообще-то и писал:
Цитата
может у кого при небольшой редакции пойдет...
- тут я имел в виду поменять типы переменных, просто кроме стандартных переменных знаю мало, а в целом-то программа работает... PS даже такую версию не компилирует, не подскажите где нормальный рабочий паскаль взять можно, а то сил моих нету с моим работать, а все что скачивал оказывалось тем же самым набором тормозов и глюков... вот такая вот беда достать в наше время рабочий паскаль((((
Автор: volvo 7.05.2006 21:35
Цитата
тут я имел в виду поменять типы переменных
Да ты сколько хочешь меняй... Что толку, если эти типы 16-битными компиляторами не поддерживаются?
Цитата
где нормальный рабочий паскаль взять можно
Паскали разные бывают...
Здесь есть ссылки на самые распространенные: http://forum.pascal.net.ru/index.php?showtopic=3699
Автор: zZz 7.05.2006 22:22
за ссылку спасибо..., вот мысль возникла может эту тему стоит в ветку программирования перенести...
Автор: lapp 8.05.2006 17:00
Цитата(zZz @ 7.05.2006 18:22)
вот мысль возникла может эту тему стоит в ветку программирования перенести...
Математические задачи вполне могут рещаться с применением программирования. И, соответственно, параллельно могут возникнуть вопросы по этому самому программированию. Мне кажется, это в порядке вещей и служит первоначально поставленной цели. Отклоняется!