загрузка...
загрузка...
На головну

I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ

  1. I.5.2) Розробка Зводу Юстиніана.
  2. Аналіз правильності алгоритмів
  3. Аналогова магнітний запис
  4. Б2. В.1 ТЕОРІЯ АЛГОРИТМІВ
  5. Буквена запис властивостей додавання і віднімання
  6. відеозапис

Для кожної з задач даного розділу потрібно розробити алгоритм вирішення задачі. Слід розглянути різні способи запису алгоритмів. Використовуйте спочатку блок-схеми - графічний спосіб зображення алгоритмів. Розробіть власну мову (жаргон) для словесного опису алгоритмів "по кроках". Для перевірки правильності складеного алгоритму слід будувати (якщо це нескладно) трасувальні таблиці, "прокручуючи" алгоритм на конкретних вихідних даних і стежачи за зміною змінних. Хоча такими налагоджувальними діями не можна довести правильність алгоритму, вони в багатьох випадках дозволяють виявити помилки в алгоритмі.

1. (Множення натуральних чисел.) Обчислити n = m ? k, Використовуючи операції додавання і а) вирахування; б) подвоєння і ділення навпіл. (Операція div ділення навпіл визначена наступним чином: r div2= s, якщо r =2s або 2s +1.)

2. (Розподіл натуральних чисел.) Обчислити приватне і залишок при діленні m на n, Використовуючи операції додавання і віднімання.

3. (Піднесення до степеня.) Для заданих цілих и  обчислити  , Використовуючи операції віднімання і множення.

4. (Обчислення "показника".) Для заданих цілих m ? 1 і n ? 2 обчислити:

а) найменше ціле k таке, що ;

б) найбільше ціле k таке, що ;

в) кількість цифр в десяткового запису числа m.

5. (Виділення квадрата.) Для заданого цілого  обчислити k - Найбільше ціле, при якому m ділиться на k2 без залишку.

6. (Виділення показника і ступеня.) Для заданих цілих чисел m,  обчислити найбільше ціле k, за якого m ділиться без залишку на: а)  ; Б) .

7. (Найбільший спільний дільник.) Обчислити d = НСД (m, n) - Найбільший спільний дільник натуральних чисел m и n, Використовуючи наступні співвідношення:

(1) якщо  , То НСД (m, n) = НСД (m-n, n);

(2) НОД (m, n) = НСД (n, m);

(3) НОД (n, 0) = n.

8. (Алгоритм Евкліда.) У задачі 7 використовувати замість (1) наступне співвідношення:

(1 ?) якщо  , То НСД (m, n) = НСД (r, n), Де r - залишок від ділення m на п.

9. (Статечної алгоритм.)

а) Обчислити у = xn (  - Ціле число), використовуючи наступне співвідношення (зведення задачі до меншому значенню n):

 якщо n парне,
 якщо n непарній,

де z = x2, - ціла частина числа , x0 = 1.

б) "Прокрутити" даний алгоритм для декількох значень n і побудувати відповідні трасувальні таблиці. Довести правильність цього алгоритму і порівняти його з алгоритмом, отриманим для завдання 3, оцінюючи (груба результати) число використовуваних операцій.

10. (Обчислення "підстави".) Для заданих цілих и  , Обчислити, використовуючи алгоритм з завдання 9:

а) найменше натуральне k, за якого ;

б) найбільше ціле k, за якого .

11. (Просте число.) Ціле число  , називається простим, Якщо його натуральними дільниками є лише 1 і саме число p (В іншому випадку число p називається складовим). Встановити, чи є задане число  простим.

вказівка: p - Просте число тоді і тільки тоді, коли жодна з цілих чисел т, для котрого  , Не є його дільником.

12. (Гіпотеза Гольдбаха.) Відповідно до відомої гіпотези будь-яке парне число  представимо у вигляді суми двох простих чисел. Встановити, чи підтверджується ця гіпотеза для заданого парного числа m.

13. (Еліптичне порівняння.) Цілі числа a и b називаються порівнянними за модулем n, Якщо їх залишки при діленні на n збігаються. Цей факт позначається як a ? b (mod n). Для заданих цілого и a, b I Zm = {0,1, ...,  } Встановити, чи має порівняння  (mod m) Хоча б одне рішення в цілих числах x, y I Zm, причому  , якщо b = 0.

14. (Простіше, ніж Велика Теорема Ферма.) Для заданих цілих m,  знайти n - Число рішень порівняння  (mod m) В цілих числах x, y, z I Zm = {0,1, ...,m-1}, x y  . (Наприклад, порівняння  (Mod 5) має 20 рішень, одне з них: x = 3, y = 1, z = 1.)

15. (Вчинені і дружні числа.)

а) Натуральне число n називається досконалим, якщо  , де  - Сума дільників числа n. (Наприклад, 6 - досконале число, так як 12 = 1 + 2 + 3 + 6.) Обчислити, скільки є скоєних чисел ? 1000000.

б) Натуральні числа a и b називаються дружніми, якщо  . Знайти всі пари (a, b) Дружніх чисел, для яких a+b < n, де n - Задане число.

16. (Теорема Лагранжа.) Будь-яке невід'ємне ціле число можна представити у вигляді суми чотирьох квадратів. (Наприклад, 7 = 12+12+12+22.) Однак для деяких чисел досить і меншого числа квадратів. (Наприклад, 4 = 22, 13 = 22+32, 6 = 12+12+22.) Обчислити, скільки (мінімально) квадратів потрібно для зазначеного подання заданого числа n.

17. (Гіпотеза Ейлера.) Леонард Ейлер припускав, що діафантово рівняння не має рішень в натуральних числах для будь-якого показника ступеня  , якщо .

Спростувати цю гіпотезу.

Підказка. Спробуйте простим перебором знайти рішення рівняння  . Рішення сущствует! Принагідно зауважимо, що є унікальний результат для s = 3, який спростовує гіпотезу Ейлера:

422 4814 = 4145604 + 2175194 + 958004.




Попередня   1   2   3   4   5   6   7   8   9   10   Наступна

ПРАКТИКУМ НА ЕОМ | III.1. Послідовна структура управління | III.2. Умовна структура управління | IV.1. Одноразові ітераційні цикли | IV.2. Перехід до кратних (вкладених) циклам | V. УПРАВЛІННЯ ПОТОКАМИ ДАНИХ | РЕКОМЕНДАЦІЇ ЩОДО відпрацювання ОСНОВНИХ ПРИЙОМІВ ПРОГРАММИРОВАНИЯ |

загрузка...
© um.co.ua - учбові матеріали та реферати