Алгоритмы, программирование

Перейти вниз

Алгоритмы, программирование

Сообщение автор Admin в Чт Сен 11, 2014 10:35 am

Длинная арифметика.
Cтандартный алгоритм.
Pascal.

Читать далее:
Стандартный алгоритм вычисления суммы длинных чисел можно оформить в виде посимвольного сложения цифр из строк и запоминанием цифры 1 для переноса в следующий разряд. Перед работой рекомендуется выровнять длину строк, т.е. заполнить строку слева нулями.
program summa;
var a,b,c:string; p,d,l1,l2,i,z,x,y:integer;
begin
readln (a); readln (b);//каждая строка чисел считывается отдельно
l1:=length (a); l2:=length (b);//определение длины строки
while l1>length(b) do b:='0'+b; l2:=length (b);
while l2>length(a) do a:='0'+a; l1:=length (a);//выравниваем длины строк
d:=0; //переменная для хранения переноса
c:=''; //результирующая строка
for i:=l2 downto 1 do begin //просматриваем с конца
 x:=ord(b[i])-ord('0'); //выделяем цифру
 y:=ord(a[i])-ord('0');
 z:=x+y+d; p:=z mod 10; d:=z div 10;//вычисление суммы и выделение разряда и переноса
 c:=chr(p+ord('0'))+c;//перевод числа в символ и добавление к сумме слева
end;
if d>0 then c:='1'+c;
writeln(c);
end.

Немного о переводе символа в число: известно, что в кодовой таблице числа как символы идут подряд от 0 до 9. Таким образом, зная только код числа 0 ord('0') и код нужного числа ord(a[i]), можно вычислить саму цифру:
  y:=ord(a[i])-ord('0');
И наоборот, зная код цифры p и нуля, можно получить символ:
  chr(p+ord('0')).

Можно воспользоваться и стандартными функциями перевода:
val(a[i],y,code); - перевод символа в число,
str(p,cp); - перевод числа в строку символов.

Но при этом нужно вводить лишние переменные:
var code:integer; cp:string;
И кроме этого с процедурой нельзя работать внутри выражений, т.е. использовать ее как функцию. В Delphi и Lazarus такая проблема снята - там есть функции:
strtoint(a[i]) и inttostr(p).

По аналогии запишем алгоритм умножения больших чисел. Здесь выравнивать числа не обящательно, а результат вычислений лучше сразу хранить в массиве чисел.
program multiplay;
type massiv =array[1..1000]of byte;
var a,b:string; c:massiv; j,i,l1,l2:integer; p,w,d,z,x,y,q:byte;
begin
readln (a); readln (b);
l1:=length (a); l2:=length (b);
w:=0;//перенос при сложении
for i:=1 to (l1+l2) do c[i]:=0;//обнуление массива
for i:=l2 downto 1 do begin
x:=ord(b[i])-ord('0');
d:=0;//перенос при умножении
for j:=l1 downto 1 do begin
y:=ord(a[j])-ord('0');
z:=x*y+d; p:=z mod 10; d:=z div 10;
q:=c[i+j]+p+w; c[i+j]:=q mod 10; w:=q div 10;
end;
if d>0 then begin q:=c[i]+w+d;c[i]:=q mod 10; w:=q div 10; end;
end;
if w>0 then begin c[1]:=w; end;
for i:=1 to (l1+l2) do write (c[i]); writeln;
end.

Все эти программы можно переписать с использованием массива или стека.
Вот пример реализации со стеком умножения длинного числа на 2. Стек реализован с помощью массива (можно и через указатели).

Например, 123456*2=246912

           6                      2

           5                      4

           4                      6

           3                      9
           2                      1

           1                      2

Const max = 501;
type arr=array[1..max] of byte;
Var  stack,result:arr;
    i: integer;
    tos: integer;
    ch:string[1];code:integer;
    ost,k,tor:integer;
{tos - содержит значение индекса для следующего помещаемого в стек эл-та}
{помещение объекта в стек }
procedure Push(i:byte;var stack:arr;var tos:integer);
begin
  if tos>=MAX then WriteLn('Stask full')
  else  begin
    stack[tos]:=i;
    tos:=tos+1;
  end;
end;

{ выборка объекта из стека }
function Pop(stack:arr; var tos:integer): byte;
begin
   tos:=tos-1;
   if tos<1 then begin
     WriteLn('Stack underflow (стек пуст)');
     tos:=tos+1;
     Pop:=0;
   end
   else Pop := stack [tos];
end;

Begin
  tos:=1;tor:=1;
  while not eoln do begin
    read(ch);  val(ch,i,code);
    if code=0 then push(i,stack,tos);
  end;
  readln;
  ost:=0;
  while tos>1 do begin
    i:=pop(stack,tos);
    k:=i*2+ost;
    i:=k mod 10;
    ost:=k div 10;
    push(i,result,tor);
  end;
  if ost<>0 then push(ost,result,tor);
  while tor>1 do write(pop(result,tor));
End.
avatar
Admin
Admin

Сообщения : 119
Дата регистрации : 2013-09-20

Посмотреть профиль http://27online.2x2forum.ru

Вернуться к началу Перейти вниз

Предложение

Сообщение автор Светлана Владимировна в Чт Сен 11, 2014 10:13 pm

Роман Николаевич, я очень рада, что вы организовали форум по разбору олимпиадных задач. Вас единицы, и если быть честными, то большинству это не нужно. Самое главное, что требуется от учителя разглядеть одаренного ребенка и направить его, другими словами составить ему маршрутную карту по сайтам и форумам, на которых эта тема обсуждается заинтересованными людьми. В Хабаровском крае существует Центр поддержки одаренных детей, на котором организованы и идут в данный момент вебинары. Ученики регистрируются и согласно расписанию выходят в назначенное время для общения с преподавателями. Предложение, может попробовать составить одаренному ученику такую карту и это я думаю будет по силам каждому учителю. Да и к портфолио пригодится.

Светлана Владимировна

Сообщения : 4
Дата регистрации : 2014-09-11

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор akaVeta в Пт Сен 12, 2014 10:51 am

Возражение
Светлана Владимировна, наверно не стоит отвечать одному - за большинство. По вашему получается следующее, учитель главное должен разглядеть одаренного ребенка , вручить ему листочек со списком сайтов, где он может чему нибудь поучиться....и умыть руки, путь его там в сети кто нибудь учит....по расписанию, в назначенное время..Для того что бы составить маршрутную карту, вовсе не нужно быть учителем информатики. Центр поддержки это замечательно и важно. Но еще важнее - рядом заинтересованный учитель,реальное общение, здесь и сейчас помощь. А показать красоту алгоритма, научить приемам и методам решения задач под силу каждому учителю информатики. А в сеть ученик выйдет и без на с вами. Для этого учитель не нужен.

akaVeta

Сообщения : 5
Дата регистрации : 2014-09-12

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор Светлана Владимировна в Пт Сен 12, 2014 9:28 pm

Уважаемая, Вета Михайловна, я отвечаю за большинство только потому, что сопровождаю наших детей на Всероссийскую олимпиаду. Наши дети приезжают туда только приглашенными, мы не проходим порог допуска, это вам о чем то говорит? Мне да. А красивые слова говорить и я умею, я констатирую факты и прошу учителей хотя бы разглядеть одаренного ребенка, не требую как вы, показать красоту алгоритма. Я очень рада, что вы это делаете, но где ваши дети, почему не видно на Всероссийской олимпиаде? Покажите ваши результаты и мы за вас порадуемся.

Светлана Владимировна

Сообщения : 4
Дата регистрации : 2014-09-11

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор akaVeta в Сб Сен 13, 2014 5:56 am

Уважаемая Светлана Владимировна я не от кого ничего не требую. Если вы сопровождаете детей на Всероссийскую олимпиаду, то вам как никому должно быть известно, почему наши дети не переходят порог. Это и малое количество часов, отведенных на программирование, и отсутствие специальных школ, как в Питере и Москве, куда дети идут после занятий и по 4-6 часов ежедневно занимаются с тренерами и их ни кто не отпихивает в сеть со списком сайтов в руках.... Вы правы, красивые слова умеем мы все говорить, вот только и детей которых вы везете, подготовили не вы лично, а тот самый заинтересованный учитель, который и красоту алгоритма показывает и душу вкладывает. Давайте не будем в очередной раз предлагать учителю написать никому ненужную бумажку, а реально поддержим.

akaVeta

Сообщения : 5
Дата регистрации : 2014-09-12

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор Светлана Владимировна в Сб Сен 13, 2014 6:50 am

Вета Михайловна, не переходите на личности. Детей который я вожу не по своей воле, готовят не учителя, это раз. Вы сами себе ответили на вопрос, что у учителя не хватает и часов, чтобы вычитать программу. Не надо извращать мои слова про маршрутные листы, вы видимо далеки от преподавательской деятельности, если называете его списком сайтов. Когда вы лично защищали свою квалификацию последний раз как учитель? Ваши ответы сами за себя говорят. Скажите честно, скольких учеников лично вы подготовили, а если подготовили, то мне бы не пришлось сопровождать их, а это делали бы вы.

Светлана Владимировна

Сообщения : 4
Дата регистрации : 2014-09-11

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор akaVeta в Сб Сен 13, 2014 9:41 am

Уважаемая Светлана Владимировна. Могу попросить и я вас о том же, не переходить на личности. Попытаюсь еще раз донести свою мысль. Всероссийская олимпиада по информатике, это такой же вид спорта, как чемпионат России по плаванию. Ни кому же не придет в голову, найти одаренного ребенка, который держится на воде лучше других, составить ему маршрутную карту по сайтам и форумам, где его бы могли обучить разным техникам заинтересованные люди, и он, согласно расписанию, в назначенное время выходил бы в сеть и учился плавать по вебинарам. А потом, ведь никому не придет в голову удивляться, почему, после такого обучения, ,он не прошел даже отборочный тур. Олимпиада это как спорт. надо ежедневно по несколько часов в день с живым тренером рядом, а лучше не одним, оттачивать движения, а в нашем случае технику решения задач. Только так можно добиться реального результата. Надо создавать школы где дети буду в реальной а не виртуальной воде учится. И пока этого не будет, не будет и побед. И маршрутная карта мало чем может помочь в данной ситуации. Не надо принимать все на свой счет. Давайте корректно и продуктивно вести диалог.

akaVeta

Сообщения : 5
Дата регистрации : 2014-09-12

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор Светлана Владимировна в Сб Сен 13, 2014 11:26 am

Очень жаль, что я привела только часть содержания, упомянув сайты и форумы. Маршрутная карта состоит не только из списка, как вы решили. Маршрутная карта одаренного ребенка состоит из индивидуальных заданий, которые подбирает ему учитель; предполагаемых участия во всевозможных дистанционный, очных и заочных олимпиадах или конкурсах и фиксированием продвижения ученика по ним.Ребенку учитель подбирает тренера или другого учителя, который занимается по этому направлению по личной инициативе и могу вас заверить если бы это делали учителя, то дети в анкете о подготовке писали бы и их фамилии. Но как показала практика не каждый учитель может составить такую карту, портфолио этому подтверждение. Я вижу пока в этом выход, не спорю надо учиться решать олимпиадные задания, но только тем кому это действительно нравится. Но зная загруженность информатиков и сколько часов выделяет школа на дополнительное образование выход в кружках. Вы правильно заметили, что плаванию за 1 час в неделю можно научить только любительски, а вот профессионально нужны другие условия и возможности.

Светлана Владимировна

Сообщения : 4
Дата регистрации : 2014-09-11

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор akaVeta в Сб Сен 13, 2014 12:19 pm

Светлана Владимировна, конечно же маршрутная карта это не только список сайтов и форумов Smile это технология для индивидуальной образовательной траектории. И учителей, которые работают с одаренными детьми - не единицы. Соглашусь с вами, что решать олимпиадные задания нужно не всем ученикам, а только тем, кому это нравится. Но маршрутная карта в аспекте Всероссийской олимпиады - все таки это не выход. Нужны другие условия.

akaVeta

Сообщения : 5
Дата регистрации : 2014-09-12

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор akaVeta в Сб Сен 13, 2014 12:34 pm

P.S. Можно еще фразу о портфолио. Вы же понимаете, что если учитель реально работает, то нет у него времени на красивые бумажки. И не потому что он не может. Да и реальная работа и слова на бумаге не всегда совпадают.

akaVeta

Сообщения : 5
Дата регистрации : 2014-09-12

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор MarinaNik в Вс Сен 14, 2014 11:15 am

Уважаемые Светлана Владимировна и Вета Михайловна! Читаю вашу переписку на форуме. Задаю себе вопрос: а вы собственно о чем, о задачах по программированию или о деятельности педагога. Если речь идет о программировании, то давайте разбирать задания и делиться опытом, как подготовить детей к олимпиаде. Если речь идет о портфолио учителя, то скажу от себя: портфолио это не красивая бумажка, а извините документ (аттестацию еще никто не отменял). Если педагог себя не ценит и в принципе не уважает свою профессию, то конечно для него это красивая бумажка. Педагог, который учит детей жить в современном мире не может себя представить? Это как минимум странно! Вопрос, обозначенный на данной ветке форума очень актуален. Как научить наших детей программированию и как научить их побеждать. Скажем честно, учителей, которые могут подготовить ребенка к такому типу заданий очень мало (учтем тот фактор, что большинство учителей информатики переучены из учителей других предметов и я знаю это наверняка), значит, действительно задача учителя информатики найти такого ученика, который будет заинтересован в изучении программирования и победе на олимпиаде. Если учитель может - пусть готовит сам, а если нет, пусть ищет способы научить (тренеры, вебинары, сетевые уроки и т.д.). А то знаете ли, ситуация очень похожа на ситуацию с ЕГЭ: готовит ребенка репетитор, а грамоты министерства и хвала с честью, почему-то, достаются учителю, который не вложил в этого ученика никакого труда (в портфолио такой учитель тоже не забудет написать о таком ученике).
Подвожу итог: на личности не переходим, вы обе грамотные методисты с большим стажем. Давайте решать задачи, которые перед нами стоят, а не препираться не понятно по какому поводу.
Ребята, давайте жить дружно!!! Very Happy

MarinaNik

Сообщения : 1
Дата регистрации : 2014-09-14

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Алгоритмы, программирование

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения