Мозжевилов Максим Александрович Разработка модулей генерации заданий и решений по теме «Основы теории чисел» диплом

Вид материала

Диплом

Содержание Вычислить НОД(a,b) при помощи бинарного алгоритма Евклида, где 2.2. Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым. 2.3. Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым. 2.4. Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым. 2.5. Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым.

Подобный материал:

• Майзаков Максим Александрович Разработка модулей автоматической генерации заданий, 799.4kb.
• Дидин Максим Александрович Переславль-Залесский Гимназия 7 7 7 7 7 7 7 7 56 диплом, 189.17kb.
• Дидин Максим Александрович Переславль-Залесский Гимназия 10 8 3 10 10 15 8 64 диплом, 103.28kb.
• hulan ucoz, 73.13kb.
• Ок. 365 300 до н э. древнегреческий математик. Работал в Александрии, 72.88kb.
• Разработка урока по теме: «Развитие мышления через постановку проблемно творческих, 84.71kb.
• Курс III семестр- VI всего аудиторных часов 69 ч.,, 47.01kb.
• Отчет о выполеннии ниокр по теме Разработка унифицированных функциональных модулей, 219.08kb.
• Рабочей программы учебной дисциплины «основы теории вероятностей и математической статистики», 46.75kb.
• Рейтинг-план освоения дисциплины «Теория принятия решений» Недели, 83.54kb.

1.3. Бинарный алгоритм Евклида.

Вычислить НОД(a,b) при помощи бинарного алгоритма Евклида, где:

а) a = 665, b = 163;

б) a = 153, b = 765;

в) a = 814, b = 661;

г) a = 508, b = 274;

д) a = 210, b = 836.

Вычислить НОД(a,b) при помощи бинарного алгоритма Евклида, где:

а) a = 665, b = 163.

Решение:

665=2⁰∙665, k₁=0; 163=2⁰∙163, k₂=0.

=> k=min(k₁,k₂)=0, a₁=max(665,163)=665, b₁=min(665,163)=163.

c=665-163=502=2¹∙251, c₁=251, a₁=max(b₁,c₁)=251, b₁=min(b₁,c₁)=163.

c=251-163=88=2³∙11, c₁=11, a₁=163, b₁=11.

c=163-11=152=2³∙19, c₁=19, a₁=19, b₁=11.

c=19-11=8=2³∙1, c₁=1, a₁=11, b₁=1.

c=11-1=10=2¹∙5, c₁=5, a₁=5, b₁=1.

c=5-1=4=2²∙1, c₁=1, a₁=1, b₁=1.

Ответ: НОД(665,163)=2^k∙b₁=2⁰∙1=1.

б) a = 153, b = 765.

Решение:

153=2⁰∙153, k₁=0; 765=2⁰∙765, k₂=0.

=> k=min(k₁,k₂)=0, a₁=max(765,153)=765, b₁=min(765,153)=153.

c=765-153=612=2²∙153, c₁=153, a₁=max(b₁,c₁)=153, b₁=min(b₁,c₁)=153.

Ответ: НОД(153,765)=2^k∙b₁=2⁰∙153=153.

в) a = 814, b = 661.

Решение:

814=2¹∙407, k₁=1; 661=2⁰∙661, k₂=0.

=> k=min(k₁,k₂)=0, a₁=max(661,407)=661, b₁=min(661,407)=407.

c=661-407=254=2¹∙127, c₁=127, a₁=max(b₁,c₁)=407, b₁=min(b₁,c₁)=127.

c=407-127=280=2³∙35, c₁=35, a₁=127, b₁=35.

c=127-35=92=2²∙23, c₁=23, a₁=35, b₁=23.

c=35-23=12=2²∙3, c₁=3, a₁=23, b₁=3.

c=23-3=20=2²∙5, c₁=5, a₁=5, b₁=3.

c=5-3=2=2¹∙1, c₁=1, a₁=3, b₁=1.

c=3-1=2=2¹∙1, c₁=1, a₁=1, b₁=1.

Ответ: НОД(814,661)=2^k∙b₁=2⁰∙1=1.

г) a = 508, b = 274.

Решение:

508=2²∙127, k₁=2; 274=2¹∙137, k₂=1.

=> k=min(k₁,k₂)=1, a₁=max(137,127)=137, b₁=min(137,127)=127.

c=137-127=10=2¹∙5, c₁=5, a₁=max(b₁,c₁)=127, b₁=min(b₁,c₁)=5.

c=127-5=122=2¹∙61, c₁=61, a₁=61, b₁=5.

c=61-5=56=2³∙7, c₁=7, a₁=7, b₁=5.

c=7-5=2=2¹∙1, c₁=1, a₁=5, b₁=1.

c=5-1=4=2²∙1, c₁=1, a₁=1, b₁=1.

Ответ: НОД(508,274)=2^k∙b₁=2¹∙1=2.

д) a = 210, b = 836.

Решение:

210=2¹∙105, k₁=1; 836=2²∙209, k₂=2.

=> k=min(k₁,k₂)=1, a₁=max(209,105)=209, b₁=min(209,105)=105.

c=209-105=104=2³∙13, c₁=13, a₁=max(b₁,c₁)=105, b₁=min(b₁,c₁)=13.

c=105-13=92=2²∙23, c₁=23, a₁=23, b₁=13.

c=23-13=10=2¹∙5, c₁=5, a₁=13, b₁=5.

c=13-5=8=2³∙1, c₁=1, a₁=5, b₁=1.

c=5-1=4=2²∙1, c₁=1, a₁=1, b₁=1.

Ответ: НОД(210,836)=2^k∙b₁=2¹∙1=2.

2. Модуль ASIMP.

2.1. Определить примерное количество простых чисел в диапазоне от a до b.

Определить примерное количество простых чисел в диапазоне от a до b, где:

а) a = 1100, b = 16000;

б) a = 4600, b = 35000;

в) a = 4400, b = 34000;

г) a = 2400, b = 13000;

д) a = 2800, b = 52000.

Определить примерное количество простых чисел в диапазоне от a до b, где:

а) a = 1100, b = 16000.

Решение:

Примерное количество простых чисел в диапазоне от 1100 до 16000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1495,76.

Ответ: K ≈ 1495,76.

б) a = 4600, b = 35000.

Решение:

Примерное количество простых чисел в диапазоне от 4600 до 35000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2799,66.

Ответ: K ≈ 2799,66.

в) a = 4400, b = 34000.

Решение:

Примерное количество простых чисел в диапазоне от 4400 до 34000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2734,07.

Ответ: K ≈ 2734,07.

г) a = 2400, b = 13000.

Решение:

Примерное количество простых чисел в диапазоне от 2400 до 13000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1064,01.

Ответ: K ≈ 1064,01.

д) a = 2800, b = 52000.

Решение:

Примерное количество простых чисел в диапазоне от 2800 до 52000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4435,89.

Ответ: K ≈ 4435,89.

2.2. Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым, если:

а) a = 2000, b = 19000;

б) a = 3800, b = 41000;

в) a = 510, b = 22000;

г) a = 3500, b = 25000;

д) a = 3700, b = 32000.

Какова вероятность того, что наугад выбранное число из диапазона от a до b будет простым, если:

а) a = 2000, b = 19000.

Решение:

Примерное количество простых чисел в диапазоне от 2000 до 19000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1665,38.

Количество чисел, больших 2000 и меньших 19000, есть 17000. Вероятность случайного выбора простого числа есть

P = 1665,38 / 17000 ≈ 0,1.

Ответ: P ≈ 0,1.

б) a = 3800, b = 41000.

Решение:

Примерное количество простых чисел в диапазоне от 3800 до 41000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3399,15.

Количество чисел, больших 3800 и меньших 41000, есть 37200. Вероятность случайного выбора простого числа есть

P = 3399,15 / 37200 ≈ 0,09.

Ответ: P ≈ 0,09.

в) a = 510, b = 22000.

Решение:

Примерное количество простых чисел в диапазоне от 510 до 22000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2118,46.

Количество чисел, больших 510 и меньших 22000, есть 21490. Вероятность случайного выбора простого числа есть

P = 2118,46 / 21490 ≈ 0,1.

Ответ: P ≈ 0,1.

г) a = 3500, b = 25000.

Решение:

Примерное количество простых чисел в диапазоне от 3500 до 25000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2039,84.

Количество чисел, больших 3500 и меньших 25000, есть 21500. Вероятность случайного выбора простого числа есть

P = 2039,84 / 21500 ≈ 0,09.

Ответ: P ≈ 0,09.

д) a = 3700, b = 32000.

Решение:

Примерное количество простых чисел в диапазоне от 3700 до 32000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2634,45.

Количество чисел, больших 3700 и меньших 32000, есть 28300. Вероятность случайного выбора простого числа есть

P = 2634,45 / 28300 ≈ 0,09.

Ответ: P ≈ 0,09.

2.3. Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым, если:

а) a = 2600, b = 31000;

б) a = 590, b = 23000;

в) a = 4900, b = 52000;

г) a = 3700, b = 20000;

д) a = 3800, b = 21000.

Какова вероятность того, что наугад выбранное нечетное число из диапазона от a до b будет простым, если:

а) a = 2600, b = 31000.

Решение:

Примерное количество простых чисел в диапазоне от 2600 до 31000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2666,91.

Количество чисел, больших 2600 и меньших 31000, есть 28400. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 14200. Вероятность случайного выбора простого числа есть

P = 2666,91 / 14200 ≈ 0,19.

Ответ: P ≈ 0,19.

б) a = 590, b = 23000.

Решение:

Примерное количество простых чисел в диапазоне от 590 до 23000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2197,62.

Количество чисел, больших 590 и меньших 23000, есть 22410. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 11205. Вероятность случайного выбора простого числа есть

P = 2197,62 / 11205 ≈ 0,2.

Ответ: P ≈ 0,2.

в) a = 4900, b = 52000.

Решение:

Примерное количество простых чисел в диапазоне от 4900 до 52000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4211,98.

Количество чисел, больших 4900 и меньших 52000, есть 47100. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 23550. Вероятность случайного выбора простого числа есть

P = 4211,98 / 23550 ≈ 0,18.

Ответ: P ≈ 0,18.

г) a = 3700, b = 20000.

Решение:

Примерное количество простых чисел в диапазоне от 3700 до 20000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1569,15.

Количество чисел, больших 3700 и меньших 20000, есть 16300. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 8150. Вероятность случайного выбора простого числа есть

P = 1569,15 / 8150 ≈ 0,19.

Ответ: P ≈ 0,19.

д) a = 3800, b = 21000.

Решение:

Примерное количество простых чисел в диапазоне от 3800 до 21000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1649,06.

Количество чисел, больших 3800 и меньших 21000, есть 17200. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 8600. Вероятность случайного выбора простого числа есть

P = 1649,06 / 8600 ≈ 0,19.

Ответ: P ≈ 0,19.

2.4. Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 3400, b = 30000;

б) a = 4300, b = 37000;

в) a = 3100, b = 39000;

г) a = 1500, b = 15000;

д) a = 1500, b = 41000.

Какова вероятность того, что наугад выбранное не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 3400, b = 30000.

Решение:

Примерное количество простых чисел в диапазоне от 3400 до 30000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2491,97.

Количество чисел, больших 3400 и меньших 30000, есть 26600. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 17733,33. Вероятность случайного выбора простого числа есть

P = 2491,97 / 17733,33 ≈ 0,14.

Ответ: P ≈ 0,14.

б) a = 4300, b = 37000.

Решение:

Примерное количество простых чисел в диапазоне от 4300 до 37000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3003,59.

Количество чисел, больших 4300 и меньших 37000, есть 32700. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 21800. Вероятность случайного выбора простого числа есть

P = 3003,59 / 21800 ≈ 0,14.

Ответ: P ≈ 0,14.

в) a = 3100, b = 39000.

Решение:

Примерное количество простых чисел в диапазоне от 3100 до 39000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3303,62.

Количество чисел, больших 3100 и меньших 39000, есть 35900. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 23933,33. Вероятность случайного выбора простого числа есть

P = 3303,62 / 23933,33 ≈ 0,14.

Ответ: P ≈ 0,14.

г) a = 1500, b = 15000.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 15000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1354,82.

Количество чисел, больших 1500 и меньших 15000, есть 13500. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 9000. Вероятность случайного выбора простого числа есть

P = 1354,82 / 9000 ≈ 0,15.

Ответ: P ≈ 0,15.

д) a = 1500, b = 41000.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 41000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3655,05.

Количество чисел, больших 1500 и меньших 41000, есть 39500. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 26333,33. Вероятность случайного выбора простого числа есть

P = 3655,05 / 26333,33 ≈ 0,14.

Ответ: P ≈ 0,14.

2.5. Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым.

Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 1500, b = 25000;

б) a = 1300, b = 34000;

в) a = 2600, b = 36000;

г) a = 2300, b = 46000;

д) a = 4200, b = 18000.

Какова вероятность того, что наугад выбранное нечетное и не кратное 3-м число из диапазона от a до b будет простым, если:

а) a = 1500, b = 25000.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 25000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2263,63.

Количество чисел, больших 1500 и меньших 25000, есть 23500. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 7833,33. Вероятность случайного выбора простого числа есть

P = 2263,63 / 7833,33 ≈ 0,29.

Ответ: P ≈ 0,29.

б) a = 1300, b = 34000.

Решение:

Примерное количество простых чисел в диапазоне от 1300 до 34000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3077,23.

Количество чисел, больших 1300 и меньших 34000, есть 32700. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 10900. Вероятность случайного выбора простого числа есть

P = 3077,23 / 10900 ≈ 0,28.

Ответ: P ≈ 0,28.

в) a = 2600, b = 36000.

Решение:

Примерное количество простых чисел в диапазоне от 2600 до 36000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3100,77.

Количество чисел, больших 2600 и меньших 36000, есть 33400. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 11133,33. Вероятность случайного выбора простого числа есть

P = 3100,77 / 11133,33 ≈ 0,28.

Ответ: P ≈ 0,28.

г) a = 2300, b = 46000.

Решение:

Примерное количество простых чисел в диапазоне от 2300 до 46000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3987,36.

Количество чисел, больших 2300 и меньших 46000, есть 43700. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 14566,67. Вероятность случайного выбора простого числа есть

P = 3987,36 / 14566,67 ≈ 0,27.

Ответ: P ≈ 0,27.

д) a = 4200, b = 18000.

Решение:

Примерное количество простых чисел в диапазоне от 4200 до 18000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1333,66.

Количество чисел, больших 4200 и меньших 18000, есть 13800. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 4600. Вероятность случайного выбора простого числа есть

P = 1333,66 / 4600 ≈ 0,29.

Ответ: P ≈ 0,29.

2.6. Сколько чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

Сколько чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 4400, b = 32000, p = 0,7;

б) a = 600, b = 41000, p = 0,99;

в) a = 3500, b = 43000, p = 0,93;

г) a = 1600, b = 49000, p = 0,5;

д) a = 1000, b = 34000, p = 0,8.

Сколько чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 4400, b = 32000, p = 0,7.

Решение:

Примерное количество простых чисел в диапазоне от 4400 до 32000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2560,31.

Количество чисел, больших 4400 и меньших 32000, есть 27600. Вероятность случайного выбора простого числа есть

P = 2560,31 / 27600 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 12,37 => n=13.

Ответ: требуется 13 испытаний.

б) a = 600, b = 41000, p = 0,99.

Решение:

Примерное количество простых чисел в диапазоне от 600 до 41000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3766,36.

Количество чисел, больших 600 и меньших 41000, есть 40400. Вероятность случайного выбора простого числа есть

P = 3766,36 / 40400 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 47,06 => n=48.

Ответ: требуется 48 испытаний.

в) a = 3500, b = 43000, p = 0,93.

Решение:

Примерное количество простых чисел в диапазоне от 3500 до 43000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3601,49.

Количество чисел, больших 3500 и меньших 43000, есть 39500. Вероятность случайного выбора простого числа есть

P = 3601,49 / 39500 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 27,82 => n=28.

Ответ: требуется 28 испытаний.

г) a = 1600, b = 49000, p = 0,5.

Решение:

Примерное количество простых чисел в диапазоне от 1600 до 49000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4320,35.

Количество чисел, больших 1600 и меньших 49000, есть 47400. Вероятность случайного выбора простого числа есть

P = 4320,35 / 47400 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 7,25 => n=8.

Ответ: требуется 8 испытаний.

д) a = 1000, b = 34000, p = 0,8.

Решение:

Примерное количество простых чисел в диапазоне от 1000 до 34000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3113,78.

Количество чисел, больших 1000 и меньших 34000, есть 33000. Вероятность случайного выбора простого числа есть

P = 3113,78 / 33000 ≈ 0,09.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 16,24 => n=17.

Ответ: требуется 17 испытаний.