Чтобы выполнять умножение многозначного числа на многозначное, необходимо уметь:

• умножать многозначное число на однозначное и на степень десяти;

• складывать многозначные числа.

• свойства сложения и умножения;

• таблицы сложения и умножения однозначных чисел.

Задача 6. Проиллюстрировать теоретические основы алгоритма умножения, вычислив произведение 537·4.

Решение. Согласно правилу записи чисел в десятичной системе счисления, 537 можно представить в виде 5·102 + 3·10 + 7 и тогда 537·4 = (5·102 + 3·10 + 7)·4. На основании дистрибутивности умножения относительно сложения раскроем скобки: (5·102)·4 + (3·10)·4 + 7·4. Далее воспользуемся коммутативностью и ассоциативностью умножения: (5·4)·102 + (3·4)·10 + (7·4). Произведения в скобках могут быть найдены по таблице умножения однозначных чисел: 20·102 + 12·10 + 28. Видим, что умножение многозначного числа на однозначное свелось к умножению однозначных чисел. Но чтобы получить окончательный результат, надо преобразовать выражение 20·102 + 12·10 + 28 - коэффициенты перед степенями числа 10 должны быть меньше 10. Для этого представим число 20 в виде 2·10, число 12 в виде 1·10 + 2, а число 28 в виде 2·10 + 8. затем в выражении (2·10)·102 + (1·10 + 2)·10 + + (2·10 + 8) раскроем скобки: 2·103 + 1·102 + 2·10 + 2·10 + 8.

На основании ассоциативности сложения и дистрибутивности умножения относительно сложения сгруппируем слагаемые 2·10 и 2·10 и вынесем 10 за скобки: 2·103 + 1·102 + (2 + 2)·10 + 8. Сумма 2 + 2 есть сумма однозначных чисел и может быть найдена по таблице сложения: 2·103 + 1·102 + 4·10 + 8. Полученное выражение есть десятичная запись числа 2148, т.е. 537·4 = 2148.

В общем виде алгоритм умножения многозначного числа на однозначное число у в столбик формулируется так:

• Записываем второе число под первым.

• Умножаем цифры разряда единиц числа х на число у. Если произведение меньше 10, его записываем в разряд единиц ответа и переходим к следующему разряду (десятков).

• Если произведение цифр единиц числа х на число у больше или равно 10, то представляем его в виде 10q1 + c0, где с0 – однозначное число; записываем с0 в разряд единиц ответа и запоминаем q1 – перенос в следующий разряд.

• Умножаем цифры разряда десятков на число у, прибавляем к полученному произведению число q1 и повторяем процесс, описанный в пункты 2 и 3.

• Процесс умножения заканчивается, когда окажется умноженной цифра старшего разряда.

Как известно, умножение числа х на число вида 10k сводится к приписыванию к десятичной записи данного числа k нулей. Покажем это.

Умножим число на 10k : . Полученное выражение является суммой разрядных слагаемых числа

так как равно .

Например, 635·103 = (6·102 + 3·10 + 5)·103 = 6·105 + 3·104 + 5·103 = = 6·105 + 3·104 + 5·103 + 0·102 + 0·10 + 0 = 635000.

Заметим еще, что умножение на число y ·10k , где у - однозначное число, сводится к умножению на однозначное число у и на число 10k . Например, 43·500 = 43·(5·102 ) = (43·5)· 102 =215·102 = 21500.

Задача 7. Проиллюстрировать алгоритм умножения многозначного числа 437 на многозначное число 254.

Решение . Представим число 254 в виде суммы 2·102 + 5·1 0+ 4 и запишем произведение 437·(2·102 + 5·10 + 4). Оно, согласно дистрибутивности умножения относительно сложения, равно 437·(2·102) + + 437·(5·10) + 437·4. Отсюда, применив ассоциативное свойство умножения, получим (437·2)·102 + (437·5)·10 + 437·4. Видим, что умножение многозначного числа 437 на многозначное число 254 свелось к умножению многозначного числа 437 на однозначные числа 2, 5 и 4, а также на степени 10. Таким образом получаем: 87400 + 21850 + 1748. Пользуясь алгоритмом сложения многозначных чисел, имеем:

Значит, 437·254 = 110998.

Сформулируем в общем виде алгоритм умножения числа на число .

1. Записываем множитель x и под ним второй множитель у.

2. Умножаем число x на младший разряд b0 числа у и записываем произведение х· b0 под числом у.

3. Умножаем число х на следующий разряд b1, числа у и записываем произведение х· b1, но со сдвигом на один разряд влево, что соответствует умножению х· b1 на 10.

4. Продолжаем вычисление произведений до вычисления х· bk .

5. Полученные k + 1 произведения складываем.

Упражнения для самостоятельной работы

1. Проиллюстрируйте теоретические основы алгоритма умножения многозначного числа на однозначное, вычислив произведение 468·3.

2. Проиллюстрируйте теоретические основы алгоритма умножения многозначного числа на многозначное, вычислив произведение 362·175.

3. Выполните умножение чисел, используя запись столбиком, и объясняя каждый шаг алгоритма: а) 873·36; в) 6030·345; б) 7365·64; г) 5478·346.

4. Используя свойства умножения, найдите наиболее рациональный способ вычисления значения выражения:

а) 8·13·4·125·25; б) 24·(27·125); в) (88 + 48)·125; г) 124·4 + 116·4;

д) (3750 - 125)·8; е) 1779·1243 - 779·1243.

5. Вычислите рациональным способом значение выражения:

а) (420 - 394)·405 - 25·405; б) 105·209 + (964 - 859)·209·400.

АЛГОРИТМ – система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому рез-ту и обладает св-вами массовости, конечности, определенности, детерминированности.

Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми (Хорезм – историческая область на территории современного Узбекистана) Пон-е алгоритма близко к другим пон-ям, таким, как метод, способ.

Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.

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

Детерминированность. При применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же рез-т.

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

Общие положения. Изучая материал концентров «Десяток», «Сотня», «Тысяча», учащиеся ознакомились с цифрами десятичной сис-мы счисления, разрядами единиц, десятков, сотен. Сейчас же им предстоит усвоить пон-е классов чисел. Это пон-е позволяет перейти к нумерации сколь угодно больших натуральных чисел. Поэтому в концентре «Многозначные числа» заканчивается изуче­ние нумерации целых неотрицательных чисел.

В предыдущих концентрах учащиеся запоминали таблицу сло­жения (вычитания), умножения (деления), овладевали приемами устного выполнения этих операций, приемами письменного сложе­ния и вычитания. В концентре «Многозначные числа» эти знания и умения обобщаются для компонентов, имеющих более трех цифр. Здесь же ученики овладевают алгоритмами письменного умножения и деления - самыми сложными в курсе матем-ки начальной школы.

Алгоритм письменного умножения.

1) Умножение в столбик. Умножение многозначного на однозначное. 125*3 - заменяем 1й множитель суммой разрядных слагаемых и умножаем сумму на число. 125*3=(100+20+5)*3 = 100*3+20*3+5*3= 300+60+15= 375. Умножение в столбик начинаем с ед. умножаем 5 ед. на 3 получаем 15 ед. Это 1 дес. и 5 ед. 5 ед. пишем ед. а 1 дес. запоминаем – ставим точку над разрядом дес.; 2 дес. умножаем на 3 ед. получаем 6 дес. плюс еще 1 дес. полуаем 7 дес. пишем 7 дес. под разр. дес.; 1 сотн. умн. на 3 получаем 3 сотни. пишем 3 сотн. под разрядом сотен. Ответ: произведение = 375.

2) Умножение многозначного числа на круглые десятки. 235*30. Число 235 сначало умножаем на 3 и полученный рез-т умножаем на 3 и полученный рез-т умножим на 10. Умножаем 235 на 3. 3*5=15. 10 ед. 1 дес. и 5 ед. 5 пишем под ед. 1 дес. запоминаем 3*3=9 да 1 получаем 10 дес. т.е. 1 сотню. и 0 дес. 1 сот. запоминаем 0 пишем под дес. 2*3 = 6 сот. да еще 1 сот. получаем 7 сот. пишем под сот. Ответ: произведение равно 705 умножаем на 10 для этого приписываем к полученному числу справа один 0. Произведение = 7050.

3). Умножение многозначного числа на сотни. 151*138 Чтобы умно. 151 на 138 надо 151 умн. на 8 151 умн. на 30. 151 умн. на 100.

4) Умножение когда 1й множитель оканчивается нулями. 235. Чтобы 235 умн. на 3 надо 5*3 =15 Единицы пишем под ед. 1 дес. запоминаем ставим точку над дес; 3 дес. умн. на 3 получаем 9 дес. + 1 дес. =1 сот. и т.д. … Затем приписываем справа 3 нуля. и 7 сот. заменяем на 7 сот. тыс.

5) Умножение многозначных чисел. когда оба числа оканчиваются нулями. тоже самое что и выше. Сначало умн. 125 на 1 получаем 5*1=5, 2*1=2 1*1=1. получаем 125 а затем к полуенному произведению приписать справа столько нулей сколько их записано в конце обоих множителей вместе.

Алгоритм письменного деления.

1) Деление многозначного числа на однозначное с остатком. 2563:5.

2563 Разделим на 5 первое неполное делимое 25 сот. В частном 3 цифры. делим 25 на 5 получаем в частном 5. 5*5 =25. 25-25=0. Ищем 2е неполное делимое. Берем 6 делим на 5 =1. 5*1 =5, 6-5=1. Приписываем 3, 13:5=2, 2*5=10, 13-10=3. 3 не делится на 5. Частное 5/2 (ост. 3)

2) Деление многозн. числа оканчивающегося нулями на однозначное. разделим на 3 первое неполное делимое = 3 тыс. в частом будет 5 цифр. и т.д. как выше. Приписываем частному 2 нуля.

3) Деление многозначного на однозначное когда значение частного выражается числом с одним или несколькими нулями в середине. 735:7=105; 735 делимое 7 делитель. Первое неполное делимое 7 сот. следовательно в частном 3 цифры. Делим 7 на 7 получаем 1. проверяем 1 неполное делимое. 1*7 получаем 7. 7-7=0. 0 пишем в частное. Сносим 3. 3 не делиться на 3. Приписываем 5. 35:7 получаем 5. 7*5=35. 35-350. Урав-е решено. Ответ: 105.

4) Деление многозначного числа на разрядное число без остатка. 3400:50=68. В частном 2 цифры узнаем дес. будет в частном. разделим 340 на 10 полученное частное 34 разделим на 5. получим 6. Узнаем сколько дес. разделим умножим 50 на 6. получим 300. Узнаем сколько дес. осталось разделить. 340-300=40. нельзя 40 дес. разделить на 50. так чтобы получилось дес. значит цфра подобрана правильно. образуем 2е неполное делимое. 40 дес. – это 400 ед. разделим 400 на 50 получим 8. из 400-400 =0. Частное 68.

5) Деление многозначного числа на 3х значное.

По исследованиям психологов оптимальный возраст для развития алгоритмического мышления школьников – 10-15 лет, т.к. он характеризуется становлением избирательности, целенаправленности восприятия, становлением устойчивого, произвольного внимания и логической памяти. В это время активно формируется абстрактное, теоретическое мышление, опирающееся на пон-я, не связанные с конкретными представлениями, развиваются гипотетико-дедуктивные процессы, появляется возможность строить сложные умозаключения, выдвигать гипотезы и проверять их. Именно формир-е мышления приводит к развитию рефлексии – способности делать предметом своей мысли саму мысль – средства, с помощью которого подросток может размышлять о себе, то есть, становится возможным развитие самосознания. Наиболее важен в этом отношении период 11-12 лет (5-6 класс) – время перехода от мышления, основанного на оперировании конкретными представлениями к мышлению теоретическому, от непосредственной памяти к логической.

Одной из педагогических задач в рамках алгоритмизации является формир-е у учеников такого пон-я как алгоритмическая культура, которое является частью общей культуры человека. Школьники, овладевшие алгоритмической культурой, хорошо понимают значение алгоритма и алгоритмического типа деят-ти, роль алгоритма в системах управления, знают основные типы алгоритмов и способы их описания, умеют нечто сложное представить через более простое.

Поэтому необходима проработка алгоритма письменного деления по карточке в соответствии со всеми правилам работы с ней. Алгоритм выполнения может содержать только описание шага, а может быть более подробным и включать в каждую операцию иллюстрацию выполнения данного шага на конкретном примере.

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

сущность пед. эксперимента всегда определяется одинаково - преднамеренное внесение в пед. процесс принципиально важных изменений в соответствии с задачей исследования, гипотезы; такой организацией пед. процесса, которая позволяет видеть связи между изучаемыми явлениями без нарушения, однако, целостного характера самого процесса; глубоким качественным анализом и по возможности более точным количественным измерением как введенных в пед. процесс новых и видоизмененных компонентов, так и рез-тов самого процесса.

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

В ходе психолого-пед. эксперимента, предполагается формир-е определенного качества (именно поэтому он еще называется "формирующий") обычно участвуют две группы: эксперементальная и контрольная. Участникам экспериментальной группы предлагается определенное задание, которое (по мнению экспериментаторов) будет способствовать формированию заданного качества. Контрольной группе испытуемых данное задание не предоставляется. В конце эксперимента две группы сравниваются между собой для оценки полученных рез-тов.

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

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

Диагностическую работу, организацию эксперимента, проведение формирующих воздействий, а также анализ полученных рез-тов, как правило, осуществляет психолог, ведущий формирующее исследование.

Тест должен обладать валидностью, обеспечивать достоверность рез-тов в отведенных для него границах: концепция теста, различные измеряемые хар-ки и прочие переменные, а также используемые в опросниках словесные формулировки. Тест должен пройти проверку на работоспособность. Валидность - соответствие рез-тов теста той хар-ке, для измерения которой он предназначен. Надёжность - св-во теста давать при повторном измерении близкие рез-ты. Надёжность как внутренняя согласованность - направленность всех элементов тестовой шкалы на измерение одного качества. Репрезентативность - соответствие между нормами (интервалами на тестовой шкале), полученными на выборке, и нормами, кот-е могут быть получены на популяции. Достоверность - св-во теста противодействовать фальсификации - намеренному или бессознательному искажению рез-тов испытуемыми.

Методы обучения – это совокупность приемов и подходов, отражающих форму взаимодействия учащихся и учителя в процессе обучения.

Метод обучения (от греч. Metodos - буквально: путь к чему-либо) - это упорядоченная деят-ть педагога и учащихся, на­правленная на достижение заданной цели обучения. Под методами обучения (дидактическими методами) часто понимают совокупность путей, способов достижения целей, решение задач образования.

Прием - это элемент метода, его составная часть, разовое действие, отдель­ный шаг в реализации метода или модификация метода в том слу­чае, когда метод простой по структуре.

Метод обучения - сложное, многомерное, многокачественное образование. В методе обучения находят отражение объективные закономерности, цели, содержание, принципы, формы обучения.

Ю.К. Бабанский все многообразие методов обучения разделил на три основные группы:

Методы организации и осуществления учебно-познавательной деят-ти;

Методы стимулирования и мотивации учебно-познавательной деят-ти;

Методы контроля и самоконтроля за эффективностью учебно-познавательной деят-ти.

Методы организации и осуществления учебно-познавательной деят-ти: Словесные Наглядные Практические (Источники) Индуктивные и дедуктивные (Логика) Репродуктивные и проблемно-поисковые (Мышление) Методы самостоятельной работы и работы под руководством преподавателя (Управление)

Общая направленность методов стимулирования учебно-познавательной деят-ти учащихся.

Методы стимулирования и мотивации учебно-познавательной деят-ти по Ю.К. Бабанскому

Методы устного контроля и самоконтроля; Методы письменного контроля и самоконтроля; Методы лабораторно-практического контроля и самоконтроля.

Хар-ка методов: а) метод эмоционального стимулирования: создание ситуаций успеха в обучении, поощрение и порицание в обучении, использование игр, игровых форм ор­ганизации учебной деят-ти, постановка сис-мы перспектив; б)метод развития познавательного интереса: формир-е готовности восприятия учебного материала, выстраивание вокруг учебного материала игрового сюжета, стимулирование занимательным содержанием, создание ситуаций творческого поиска; в) формир-е ответственности и обязательности: формир-е личной значимости учения, предъявление учебных требова­ний, оперативный контроль.

Умножение однозначных чисел можно выполнить, основываясь на определении этого действия. Но чтобы всякий раз не обращаться к определению, все произведения однозначных чисел записывают в особую таблицу, называемую таблицей умножения однозначных чисел, и запоминают.

Естественно, что смысл умножения сохраняется и для многозначных чисел, но меняется техника вычислений. Произведение многозначных чисел, как правило, находят, выполняя умножение столбиком, по определенному алгоритму. Выясним, каким образом возника­ет этот алгоритм, какие теоретические факты лежат в его основе.

Умножим, например, столбиком 428 на 263.

Видим, что для получения ответа нам пришлось умножить 428 на 3, 6 и 2, т.е. умножить многозначное число на однозначное; но, умножив на 6, результат записали по - особому, поместив единицы числа 2568 под десятками числа 1284, так как умножали на 60 и получили число 25680, но нуль в конце записи опустили. Слагаемое 856 - это результат умножения на 2 сотни, т.е. число 85600. Кроме того, нам пришлось найти сумму многозначных чисел.

Итак, чтобы выполнять умножение многозначного числа на многозначное, необходимо уметь:

Умножать многозначное число на однозначное и на степень десяти;

Складывать многозначные числа.

Сначала рассмотрим умножение многозначного числа на однозначное.

Умножим, например, 428 на 3. Согласно правилу записи чи­сел в десятичной системе счисления, 428 можно представить в виде 4 × 10 2 + 2 × 10 + 8 и тогда 428× 3 = (4× 10 2 + 2 × 10+ 8)× 3. На основании дистрибутивности умножения относительно сложения раскроем скобки: (4 × 10 2 + (2× 10)× 3 + 8 × 3. Произведения в скобках могут быть найде­ны по таблице умножения однозначных чисел: 12× 10 2 + 6 × 10 + 24. Видим, что умножение многозначного числа на однозначное свелось к умножению однозначных чисел. Но чтобы получить окончательный результат, надо преобразовать выражение 12× 10 2 + 6 × 10 + 24 - коэф­фициенты перед степенями 10 должны быть меньше 10. Для этого представим число 12 в виде 1 ·10 + 2, а число 24 в виде 2·10 + 4. Затем в выражении (1·10 + 2) ·10 2 + 6·10 + (2·10 + 4) раскроем скобки: 1·10 3 +2·10 2 +6·10+2·10+4. На основании ассоциативности сложения и дистрибутивности умножения относительно сложения сгруппируем слагаемые 6·10 и 2·10 и вынесем 10 за скобки: 1·10 3 + 2·10 2 + (6 + 2) ·10+4. Сумма 6+2 есть сумма однозначных чисел и может быть найдена по таблице сложения: 1 · 10 3 + 2·10 2 + 8 ·10 + 4. Полученное выражение есть десятичная запись числа 1284, т. е. 428·3 = 1284.

Таким образом, умножение многозначного числа на однозначное основывается на:

Записи чисел в десятичной системе счисления;

Свойствах сложения и умножения;

Таблицах сложения и умножения однозначных чисел.

Выведем правило умножения многозначного числа на однозначное в общем виде.

Пусть требуется умножить х = а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0 на однозначное число у:

х × у = (а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0) × у = (а n × у) × 10 n +(а n – 1 × у) × 10 n – 1 + … + а 0 × у причем преобразования выполнены на основании свойств умножения. После этого, используя таблицу умножения, заменяем все произведения а k × у, где 0 £ k £ n, соответствующими значениями а k × у = b k ×10 + с и получаем: х× у = (b п ×10 + с п) + (b п - 1 ×10+ с п - 1) ×10 п - 1 + ... +(b 1 ×10 + с 1) ×10 + (b 0 ×10 + с 0) = b п ×10 п + 1 + (с п + b п - 1) ×10 п + ... + (с 1 + b 0) ×10 + с 0 . По таблице сложения заменяем суммы с k + b k - 1 , где 0 £ k £ n и k = 0, 1, 2, ..., n, их значениями. Если, например, с 0 однозначно, то последняя цифра произведения равна с 0 . Если же с 0 = 10 + m 0 , то последняя цифра равна m 0 , а к скобке (с 1 + b 0) надо прибавить 1. Продолжая этот процесс, получим десятичную запись числа х × у.

Описанный процесс позволяет сформулировать в общем видеалгоритм умножения многозначного числа на однозначное число у.

1. Записываем второе число под первым.

2. Умножаем цифры разряда единиц числа х на число у. Еслипроизведение меньше 10, его записываем в разряд единиц ответа и переходим к следующему разряду (десятков).

3. Если произведение цифр единиц числа х на число у большеили равно 10, то представляем его в виде 10q 1 + с 0 , где с 0 – однозначное число; записываем с 0 в разряд единиц ответа и запоминаем q 1 - перенос в следующий разряд.

4. Умножаем цифры разряда десятков на число у, прибавляемк полученному произведению число q 1 и повторяем процесс, описанный пп. 2 и 3.

5. Процесс умножения заканчивается, когда окажется умноженной цифра старшего разряда.

Как известно, умножение числа х на число вида 10 k сводится к приписыванию к десятичной записи данного числа k нулей. Покажем это. Умножим число х = а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0 на 10 k: (а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0) × 10 k = а n × 10 n+ k + а n – 1 × 10 n+ k – 1 + …+ а 0 × 10 k . Полученное выражение является суммой разрядных слагаемых числа , так как равно a n × 10 n+ k + а n – 1 × 10 n+ k – 1 + …+ а 0 × 10 k + 0 ×10 k -1 + 0× 10 k –2 + …+ 0× 10 + 0.

Например ,

347·10 3 =(3·10 2 +4·10+7)·10 3 =3·10 5 +4·10 4 +7·10 3 =3·10 5 +4·10 4 +7·10 3 +0·10 2 +0·10+0= =347000

Заметим еще, что умножение на число у× 10 k , где у – однозначное число сводится к умножению на однозначное число у и на число 10 k . Например, 52×300 = 52×(3×10 2) = (52×3) ×10 2 = 156×10 2 = 15600.

Рассмотрим теперь алгоритм умножения многозначного числа на многозначное. Обратимся сначала к примеру, с которого начинали, т.е. к произведению 428× 263. Представим число 263 в виде суммы 2× 10 2 + 6× 10 + 3 и запишем произведение 428× (2× 10 2 + 6× 10 + 3). Оно, согласно дистрибутивности умножения относительно сложения, равно 428× (2× 10 2) + 428× (6× 10) + 428× 3. Отсюда, применив ассоциативное свойство умножения, получим: (428× 2) × 10 2 + (428× 6) × 10 + 428× 3. Видим, что умножение многозначного числа 428 на многозначное число 263 свелось к умножению многозначного числа 428 на однозначные числа 2,6 и 3, а также на степени 10.

Рассмотрим умножение многозначного числа на многозначное в общем виде.

Пусть х и у - многозначные числа, причем у = b m × 10 m + b m – 1 × 10 m – 1 + …+ b 0 . В силу дистрибутивности умножения относитель­но сложения, а также ассоциативности умножения можно записать:

х× у = х× (b m × 10 m + b m – 1 × 10 m – 1 + …+ b 0) = (х× b m) × 10 m + (х× b m – 1)× 10 m – 1 + …+ b 0 × х. Последовательно умножая число х на однозначные числа b m , b m – 1 , …, b 0 , а затем на 10 m , 10 m – 1 , …, 1, получаем слагаемые, сумма которых равна х× у.

Сформулирует в общем виде алгоритм умножения числа х = на число у = .

1. Записываем множитель х под ним второй множитель у.

2. Умножаем число х на младший разряд b 0 числа у и записываем произведение х × b 0 под числом у.

3. Умножаем число х на следующий разряд b 1 числа у и записываем произведение х × b 1 , но со сдвигом на один разряд влево, что соответствует умножению х × b 1 на 10.

4. Продолжаем вычисление произведений до вычисления х × b k .

5. Полученные k + 1 произведения складываем.

Изучение алгоритма умножения многозначных чисел в начальном курсе математики, как правило, проходит в соответствии с выделенными этапами. Различия имеются только в записи. Например, при обосно­вании случая умножения многозначного числа на однозначное пишут:

428 × 3 = (400 + 20 + 8) × 3 == 400× 3 + 20× 3 + 8× 3 == 1200 + 60 + 24 = 1284.

Основой выполненных преобразований являются:

Представление первого множителя в виде суммы разрядных слагаемых (т.е. запись числа в десятичной системе счисления);

Правило умножения суммы на число (или дистрибутивность умножения относительно сложения);

Умножение «круглых» (т.е. оканчивающихся нулями) чиселна однозначное число, что сводится к умножению однозначных чисел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ НАУКИ И СПОРТА УКРАИНЫ

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Факультет Компьютерной инженерии и управления

Кафедра Безопасности информационных систем

КУРСОВАЯ РАБОТА

Дисциплина: Технологии программирования

Тема: Реализация операции возведения в квадрат для больших целых чисел с использованием «классического алгоритма»

Выполнил:

студент I курса

группы БИКС-12-2

Кареба Иван Сергеевич

Научный руководитель:

Мельникова Оксана Анатольевна

Харьков 2013

Харьковский национальный университет радиоэлектроники

Факультет: КИУ

Кафедра: Безопасность информационных технологий

Специальность: “Безопасность информационных и коммуникационных систем”

Дисциплина: “Технологии программирования”

УТВЕРЖДАЮ

Зав. кафедры БИТ

проф. И.Д. Горбенко

НА КУРСОВУЮ РАБОТУ

Студенту

Кареба Ивану Сергеевичу

Тема работы: Реализация операции возведения в квадрат для больших целых чисел с использованием «классического алгоритма».

Срок сдачи студентом законченной работы: .

Исходные данные к проекту:

Перечень графического материала: отсутсвует

________________________________________________________________

Основная литература и источники:

Дата выдачи задания: 25.02.2013

Дата сдачи задания: 25.05.2013

Руководитель работы: Мельникова Оксана Анатольевна

Задание принял к выполнению _______________________________

(подпись студента)

Студент: Кареба Иван Сергеевич _________

(подпись)

Курсовая работа содержит 25 стр., 6 источников, 1 приложение, 6 рисунков.

Объектом исследования является операция возведения в квадрат больших целых чисел.

Предметом исследования является программная реализация операции возведения в квадрат больших целых чисел.

Основной задачей работы является реализация операции возведения в квадрат больших целых чисел (от 512 бит) с использованием классического алгоритма, то есть умножения «в столбик».

ВОЗВЕДЕНИЯ В КВАДРАТ, КЛАССИЧЕСКИЙ АЛГОРИТМ УМНОЖЕНИЯ, ДЛИННАЯ АРИФМЕТИКА,. ДОНАЛЬД КНУТ, VISUAL STUDIO 2012

ВВЕДЕНИЕ

ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ

Кнут, его вклад в развитие вычислительных алгоритмов, для ЭВМ

«Классические алгоритмы» Дональда Кнута

1. «Классический алгоритм» операции сложения-вычитания

   «Классический алгоритм» операции умножения

   «Классический алгоритм» операции деления

1.3 Алгоритм Фюрера

1.4 История возникновения степени числа

ОПИСАНИЕ ПРОГРАММЫ

2.1 Общие сведения

2.2 Функциональное назначение

2.3 Описание логической структуры

2.4 Используемые технические средства

2.6 Входные и выходные данные

ПЕРЕЧЕНЬ ССЫЛОК

ПРИЛОЖЕНИЕ А

ВВЕДЕНИЕ

С развитием науки и всего человечества, появилась потребность в быстрой работе с большими числами. Создавались и придумывались различные алгоритмы позволяющие быстро складывать, вычитать, умножать, делить и так далее. Это была сложная и кропотливая работа – сидеть и считать такие числа. Поэтому человечество упрощала эту работу различными приборами, помогающими считать: таблиц, счеты и так далее…

Одним из таких приборов была ЭВМ. Она делала все эти операции за считанные секунды, что в значительной мере ускорило развитие наук. Вскоре наука так стремительно развинулась, что и для компьютера арифметические операции стали непосильной задачей. Проблема была с ограниченной памятью разрядной сетки: 8 бит, 16 бит, 32 бит, а в скорее и 64 бит. Но этого было мало.

И в ХХ веке заслуженный профессор, математик и программист, а также «отец» основных алгоритмов вычислительной математики Дональд Эрвин Кнут разработал серию так называемых «Классических алгоритмов» для арифметических операций с использованием ЭВМ.

Эти алгоритмы помогли компьютерам имея разрядность значительно меньшую разрядности вычисляемых чисел давать верный ответ над многими арифметическими операциями.

В основу этих алгоритмов легли школьные алгоритмы: сложение, вычитание, умножение «в столбик», деление «уголком» и прочее, что многие дети изучают в школе.

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

1 Используемые методы и алгоритмы

Кнут, его вклад в развитие вычислительных алгоритмов, для ЭВМ.

Дональд Эрвин Кнут (англ. Donald Ervin Knuth, МФА: /kəˈnuːθ/, родился 10 января 1938) - американский учёный, почётный профессор в отставке (professor emeritus) Стэнфордского университета и нескольких других университетов в разных странах, иностранный член Российской академии наук, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике (в первую очередь - физико-математических).

Рисунок 1.1 – «Дональд Эрвин Кнут»

«Искусство программирования» том 1 - Основные алгоритмы, «Искусство программирования» том 2 - Получисленные методы, «Искусство программирования» том 3 - Сортировка и поиск, «Искусство программирования» том 4 - Комбинаторные алгоритмы.

В этих книгах описываются всевозможные алгоритмы и методы работы с ЭВМ, упрощающие и дающие более широкий спектр ресурсов.

Для разработки этих методов и алгоритмов требуется необычайно творческий склад ума, а также доскональное понимание алгебры, высшей математики и абстрактной алгебры. Все это присутствовало в сознании Дональда Эрвина, что принципе и позволило ему создать свои алгоритмы.

Его так называемые «Классические алгоритмы» пользовались огромным спросом, и не удивительно.

«Классические алгоритмы» Дональда Кнута.

В этом разделе будут рассмотрены алгоритмы следующих операций:

Сложение и вычитание n-разрядных целых чисел с получением n-разрядного результата и разряда переноса;

Умножение m-разрядного целого числа на n-разрядное целое число с получением (m+n)-разрядного результата;

Деление (m+n)-разрядного числа на n-разрядного числа с получением (m+1)-разрядного частного и n-разрядного остатка.

Эти алгоритмы можно назвать классическими, так как само слово “алгоритм” на протяжении столетий использовалось в связи с реализацией вычислительных процессов. Термин “n-разрядное целое число” означает любое неотрицательное целое число, меньшее b^n, где b есть основание обычной позиционной системы счисления, в которой представляются числа; такие числа в этой системе записываются с использованием не более чем n-“разрядов”.

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

В настоящем разделе будут рассмотрены алгоритмы выполнения перечисленных операций над целыми числами, представляемыми в позиционной системе по основанию b, где b - заданное целое число, равное или большее 2. Таким образом, эти алгоритмы представляют собой достаточно общие определения арифметических процессов, и в этом качестве они не связаны ни с какой конкретной вычислительной машиной. Тем не менее, рассуждения будут некоторым образом машинно-ориентированными, поскольку нас, в основном, интересуют эффективные методы выполнения при помощи компьютера вычислений с высокой точностью. Хотя приведенные примеры ориентированы на гипотетический компьютер М1Х, по существу, те же рассуждения применимы почти для любой другой машины.

Для понимания сути чисел повышенной точности наиболее существенно то, что их можно рассматривать как числа, записанные в системе счисления по основанию w, где w - размер слова. Например, целое число, заполняющее 10 машинных слов в памяти компьютера, размер слова которой - w = 10^10, имеет 100 десятичных разрядов. Однако мы будем рассматривать его как 10-разрядное число по основанию 10^10. Такой подход обосновывается теми же соображениями, что и переход, скажем, от двоичной системы счисления к шестнадцатеричной; мы просто группируем биты.

С учетом этих соглашений будем рассматривать следующие элементарные операции:

А) сложение и вычитание одноразрядных целых чисел с получением одноразрядного результата и разряда переноса;

B) умножение одноразрядного целого числа на одноразрядное с получением двухразрядного результата;

С) деление двухразрядного целого числа на одноразрядное, которое обеспечивает получение частного как одноразрядного целого числа и одноразрядного остатка.

В связи с тем, что целые числа повышенной точности воспринимаются как числа по основанию b, полезно представить себе соответствующую ситуацию при Ь = 10, считая при этом, что арифметические операции выполняются вручную. Тогда операция A аналогична запоминанию таблицы сложения, операция B аналогична запоминанию таблицы умножения, а операция C - это, по существу, запоминание “обращенной” таблицы умножения. Более сложные операции A, B и C над числами высокой точности могут быть теперь реализованы на основе простых операций сложения, вычитания, умножения и деления в столбик, которым учат детей в начальной школе. Фактически большинство алгоритмов, которые будут рассматриваться ниже, - не что иное, как механическое воспроизведение знакомых операций, выполняемых при помощи карандаша и бумаги. Конечно, алгоритмы придется формулировать гораздо более тщательно, чем в начальной школе. Кроме того, необходимо стремиться минимизировать используемую машинную память и время, затрачиваемое на выполнение программ.

«Классический алгоритм» операции сложения-вычитания.

Из-за сложности перевода книги из одного формата в другой и сложности написания формул, я предоставлю алгоритм в виде рисунка.

Рисунок 1.2 – «Представление «Классического алгоритма» сложения, основанного на размышлениях Дональда Эрвина Кнута»

Задача вычитания аналогична задаче сложения, но есть и заслуживающие внимания отличия.

Рисунок 1.3 – ««Представление «Классического алгоритма» вычитания, основанного на размышлениях Дональда Эрвина Кнута»

Эрвин Кнут, в своей книге советует не создавать одну комбинированную программу, для сложения-вычитания, а создать две абсолютно независимых программы. Он поясняет это тем, что в общем случае для реализации этих операций предпочтительнее использовать две разные программы, чтобы внутренний вычислительный цикл выполнялся настолько быстро, насколько это возможно.

«Классический алгоритм» операции умножения.

Наша следующая задача-умножение. Здесь идеи, использованные при построении алгоритма А, получают дальнейшее развитие.

Рисунок 1.4 – «Первая часть алгоритма умножения»

Алгоритм B - не самый быстрый способ умножения, если множители m и n велики, хотя он имеет преимущество (он прост).

Рисунок 1.5 – «Вторая часть алгоритма умножения»

Описанный процесс позволяет сформулировать в общем виде алгоритм вычитания чисел в десятичной системе счисления.

1. Записываем вычитаемое под уменьшаемым так, чтобы соответствующие разряды находились друг под другом.

2. В случае если цифра в разряде единиц вычитаемого не превосходит соответствующей цифры уменьшаемого, вычитаем ее из цифры уменьшаемого, записываем разность в разряд единиц искомого числа, после чего переходим к следующему разряду.

3. В случае если же цифра единиц вычитаемого больше единиц уменьшае­мого, ᴛ.ᴇ. b 0 >а 0 , а цифра десятков уменьшаемого отлична от нуля, то уменьшаем цифру десятков уменьшаемого на 1, одновременно увеличив цифру единиц уменьшаемого на 10, после чего вычитаем из числа 10 + а 0 число b 0 и записываем разность в разряде единиц ис­комого числа, далее переходим к следующему разряду.

4. В случае если цифра единиц вычитаемого больше цифры единиц уменьшаемого, стоящие в разряде десятков, сотен и т.д. уменьшаемого, равны нулю, то берем первую отличную от нуля цифру в уменьшаемом (после разряда единиц), уменьшаем ее на 1, всœе цифры в младших разрядах до разряда десятков включительно увеличиваем на 9, а цифру в разряде единиц на 10: вычитаем b 0 из 10 + а 0 , записываем разность в разряде единиц искомого числа и переходим к следующему разряду.

5. В следующем разряде повторяем описанный процесс.

6. Вычитание заканчивается, когда производится вычитаниеизстаршего разряда уменьшаемого.

Умножение однозначных чисел можно выполнить, основываясь на определœении этого действия. Но чтобы всякий раз не обращаться к определœению, всœе произведения однозначных чисел записывают в особую таблицу, называемую таблицей умножения однозначных чисел, и запоминают.

Естественно, что смысл умножения сохраняется и для многозначных чисел, но меняется техника вычислений. Произведение многозначных чисел, как правило, находят, выполняя умножение столбиком, по определœенному алгоритму. Выясним, каким образом возника­ет данный алгоритм, какие теоретические факты лежат в его основе.

Умножим, к примеру, столбиком 428 на 263.

Видим, что для получения ответа нам пришлось умножить 428 на 3, 6 и 2, ᴛ.ᴇ. умножить многозначное число на однозначное; но, умножив на 6, результат записали по - особому, поместив единицы числа 2568 под десятками числа 1284, так как умножали на 60 и получили число 25680, но нуль в конце записи опустили. Слагаемое 856 - это результат умножения на 2 сотни, ᴛ.ᴇ. число 85600. Вместе с тем, нам пришлось найти сумму многозначных чисел.

Итак, чтобы выполнять умножение многозначного числа на многозначное, крайне важно уметь:

Умножать многозначное число на однозначное и на степень десяти;

Складывать многозначные числа.

Сначала рассмотрим умножение многозначного числа на однозначное.

Умножим, к примеру, 428 на 3. Согласно правилу записи чи­сел в десятичной системе счисления, 428 можно представить в виде 4× 10 2 +2× 10+8 и тогда 428× 3=(4× 10 2 +2× 10+8)× 3. На основании дистрибутивности умножения относительно сложения раскроем скобки: (4× 10 2 +(2× 10)× 3+8× 3. Произведения в скобках бывают найде­ны по таблице умножения однозначных чисел: 12× 10 2 +6× 10+24. Видим, что умножение многозначного числа на однозначное свелось к умножению однозначных чисел. Но чтобы получить окончательный результат, нужно преобразовать выражение 12× 10 2 +6× 10+24 - коэф­фициенты перед степенями 10 должны быть меньше 10. Для этого представим число 12 в виде 1·10+2, а число 24 в виде 2·10+4. Затем в выражении (1·10+2)·10 2 +6·10+(2·10+4) раскроем скобки: 1·10 3 +2·10 2 +6·10+2·10+4. На основании ассоциативности сложения и дистрибутивности умножения относительно сложения сгруппируем слагаемые 6·10 и 2·10 и вынесем 10 за скобки: 1·10 3 +2·10 2 +(6+2)·10+4. Сумма 6+2 есть сумма однозначных чисел и может быть найдена по таблице сложения: 1· 10 3 +2·10 2 +8·10+4. Полученное выражение есть десятичная запись числа 1284, т. е. 428·3=1284.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, умножение многозначного числа на однозначное основывается на:

Записи чисел в десятичной системе счисления;

Свойствах сложения и умножения;

Таблицах сложения и умножения однозначных чисел.

Выведем правило умножения многозначного числа на однозначное в общем виде.

Пусть требуется умножить х=а n ×10 n +а n–1 ×10 n–1 +…+а 1 ×10+а 0 на однозначное число у:

х×у=(а n ×10 n +а n–1 ×10 n–1 +…+а 1 ×10+а 0)×у=(а n ×у)×10 n +(а n–1 × у)×10 n–1 +…+а 0 ×у причем преобразования выполнены на основании свойств умножения. После этого, используя таблицу умножения, заменяем всœе произведения а k ×у, где 0£k£n, соответствующими значениями а k ×у=b k ×10+с и получаем:

х×у=(b п ×10+с п)+(b п-1 ×10+с п-1)×10 п-1 +...+(b 1 ×10+с 1)×10+(b 0 ×10+с 0)= =b п ×10 п+1 +(с п +b п-1)×10 п +...+(с 1 +b 0)×10+с 0 . По таблице сложения заменяем суммы с k +b k -1 , где 0£k£n и k=0,1,2, ...,n, их значениями. В случае если, к примеру, с 0 однозначно, то последняя цифра произведения равна с 0 . В случае если же с 0 =10+m 0 , то последняя цифра равна m 0 , а к скобке (с 1 + b 0) нужно прибавить 1. Продолжая данный процесс, получим десятичную запись числа х × у.

Описанный процесс позволяет сформулировать в общем видеалгоритм умножения многозначного числа на однозначное число у.

1. Записываем второе число под первым.

2. Умножаем цифры разряда единиц числа х на число у. В случае еслипроизведение меньше 10, его записываем в разряд единиц ответа и переходим к следующему разряду (десятков).

3. В случае если произведение цифр единиц числа х на число у большеили равно 10, то представляем его в виде 10q 1 +с 0 , где с 0 – однозначное число; записываем с 0 в разряд единиц ответа и запоминаем q 1 - перенос в следующий разряд.

4. Умножаем цифры разряда десятков на число у, прибавляемк полученному произведению число q 1 и повторяем процесс, описанный пп. 2 и 3.

5. Процесс умножения заканчивается, когда окажется умноженной цифра старшего разряда.

Как известно, умножение числа х на число вида 10 k сводится к приписыванию к десятичной записи данного числа k нулей. Покажем это. Умножим число х=а n ×10 n +а n–1 ×10 n–1 +…+а 1 ×10+а 0 на 10 k:

(а n ×10 n +а n–1 ×10 n–1 +…+а 1 ×10+а 0)×10 k =а n ×10 n+ k +а n–1 ×10 n+ k –1 +…+а 0 ×10 k . Полученное выражение является суммой разрядных слагаемых числа , так как равно

a n ×10 n+ k +а n–1 ×10 n+ k –1 +…+а 0 ×10 k +0×10 k -1 +0×10 k –2 +…+0×10 +0.

К примеру ,

347·10 3 =(3·10 2 +4·10+7)·10 3 =3·10 5 +4·10 4 +7·10 3 =3·10 5 +4·10 4 +7·10 3 +0·10 2 + +0·10+0= =347000

Заметим еще, что умножение на число у×10 k , где у – однозначное число сводится к умножению на однозначное число у и на число 10 k . К примеру, 52×300=52×(3×10 2)=(52×3)×10 2 =156×10 2 =15600.

Рассмотрим теперь алгоритм умножения многозначного числа на многозначное. Обратимся сначала к примеру, с которого начинали, ᴛ.ᴇ. к произведению 428× 263. Представим число 263 в виде суммы 2× 10 2 +6× 10+3 и запишем произведение 428× (2× 10 2 + 6× 10 + 3). Оно, согласно дистрибутивности умножения относительно сложения, равно 428× (2× 10 2) + 428× (6× 10) + 428× 3. Отсюда, применив ассоциативное свойство умножения, получим: (428× 2) × 10 2 +(428× 6)× 10+428× 3. Видим, что умножение многозначного числа 428 на многозначное число 263 свелось к умножению многозначного числа 428 на однозначные числа 2,6 и 3, а также на степени 10.

Рассмотрим умножение многозначного числа на многозначное в общем виде.

Пусть х и у - многозначные числа, причем у=b m ×10 m +b m –1 ×10 m –1 +…+b 0 . В силу дистрибутивности умножения относитель­но сложения, а также ассоциативности умножения можно записать:

х×у=х×(b m ×10 m +b m –1 ×10 m –1 +…+b 0)=(х×b m)×10 m +(х×b m –1)×10 m –1 +…+b 0 ×х. Последовательно умножая число х на однозначные числа b m , b m –1 , …, b 0 , а затем на 10 m , 10 m –1 , …, 1, получаем слагаемые, сумма которых равна х× у.

Сформулирует в общем виде алгоритм умножения числа х= на число у = .

1. Записываем множитель х под ним второй множитель у.

2. Умножаем число х на младший разряд b 0 числа у и записываем произведение х × b 0 под числом у.

3. Умножаем число х на следующий разряд b 1 числа у и записываем произведение х×b 1 , но со сдвигом на один разряд влево, что соответствует умножению х × b 1 на 10.

4. Продолжаем вычисление произведений до вычисления х×b k .

5. Полученные k+1 произведения складываем.

Изучение алгоритма умножения многозначных чисел в начальном курсе математики, как правило, проходит в соответствии с выделœенными этапами. Различия имеются только в записи. К примеру, при обосно­вании случая умножения многозначного числа на однозначное пишут:

428 × 3 = (400 + 20 + 8) × 3 = 400× 3 + 20× 3 + 8× 3 = 1200 + 60 + 24 = 1284.

Основой выполненных преобразований являются:

Представление первого множителя в виде суммы разрядных слагаемых (ᴛ.ᴇ. запись числа в десятичной системе счисления);

Правило умножения суммы на число (или дистрибутивность умножения относительно сложения);

Умножение «круглых» (ᴛ.ᴇ. оканчивающихся нулями) чиселна однозначное число, что сводится к умножению однозначных чисел.