Матеріали для Нової української школи 1 клас - планування, розробки уроків, дидактичні та методичні матеріали, підручники та зошити

МАТЕМАТИКА Й МАТЕМАТИЧНА СТАТИСТИКА - Золота колекція рефератів - 2018

КОДИ ГРЕЯ Й АНАЛОГІЧНІ ЗАВДАННЯ

Можливість практичного виконання програм з кодами Грея не є неодмінною умовою вивчення програмування. Однак вона є найсильнішим стимулом, без якого навряд чи в кого вистачить інтересу й терпіння.

Іноді буває корисно перераховувати об’єкти в такому порядку, щоб кожний наступний мінімально відрізнявся від попередніх.

Розглянемо кілька задач такого типу.

Задача 1. Перерахувати всі послідовності довжини n із чисел 1 ... k в такому порядку, щоб кожна наступна відрізнялася віл попередньої лише одною цифрою, причому не більше ніж на 1.

Розв’язання. Розглянемо прямокутну дошку шириною n і висотою k. На кожній вертикалі стоятиме шашка. Таким чином, положення шашок відповідають послідовностям із чисел 1 ... k довжини n (5-й член послідовності відповідає висоті шашки на 5-ій горизонталі). На кожній шашці намалюємо стрілочку, що може бути спрямована вгору або вниз. Спочатку всі шашки поставимо на нижню горизонталь стрілочкою вгору. Далі рухаємо шашки за таким правилом: знайшовши найправішу шашку, яку можна підсунути в напрямку намальованої на ній стрілки, рухаємо її па одну клітинку в цьому напрямку, а всі шашки, що стоять праворуч від неї (вони вперлися в край), розвертаємо кругом.

Зрозуміло, що па кожному кроці тільки одна шашка зрушується, тобто один член послідовності змінюється на 1. Доведемо індукцією по п, що проходяться всі послідовності з чисел 1... k. Випадок n= 1 є очевидним. Нехай n > 1. Усі ходи поділимо на ті, де рухається остання шашка, і ті, де рухається не остання. У другому випадку остання шашка стоїть біля стіни, і ми її повертаємо, так що за кожним ходом другого типу іде k - 1 ходів першого типу, під час яких остання шашка побуває в усіх клітинках. Якщо ми тепер забудемо про останню шашку, то рухи перших n - 1 з припущення індукції проходять всі послідовності довжини n - 1 по одному разу; натомість рухи останньої шашки з кожної послідовності довжини n - 1 роблять k послідовностей довжини n.

У програмі, крім послідовності х [1] ... х [n], будемо зберігати масив d[1] ... d[n] із чисел +1 і -1 (+1 відповідає стрілці вгору,-1 — стрілці вниз).

Початковий стан: x[ 1] =... = x[n] = 1; d(1] = ... = d[n] = 1.

Наведемо алгоритм переходу до наступної послідовності (одночасно з’ясовується, чи можливий він, — відповідь стає значенням булевської змінної р).

Зауваження. Для послідовностей нулів і одиниць можливе інше розв’язання, що використовує двійкову систему (саме воно пов’язується зазвичай з назвою «коди Грея»).

Запишемо підряд всі числа від 0 до -1 у двійковій системі (2 у степені n). Наприклад, для n = 3 напишемо:

000 001 010 011 100 101 110 111

Потім кожне з чисел піддамо перетворенню, замінивши кожну цифру, крім першої, на її суму з попередньою цифрою (за модулем 2).

Іншими словами, число

a [ 1 ], a [ 2 ], …а [ n ] перетворимо на a [ 1 ], a [ 1 ] + а [ 2 ], a [ 2 ] + a [ 3 ], …, а [ n -1] + a [ n ]

(сума за модулем 2).

Для n = 3 одержимо: 000 001 011 010 110 111 101 100.

Легко перевірити, що описане перетворення чисел оборотне (і в такий спосіб дає всі послідовності по одному разу).

Крім того, двійкові записи сусідніх чисел відрізняються заміною кінцевих чисел 011... 1 на кінцеві числа 100...0, що після перетворення призводить до зміни лише одної цифри.

Застосування коду Грея

Нехай є обертова вісь, і ми хочемо поставити датчик кута повороту цієї осі. Насадимо на вісь барабан, пофарбуємо половину барабана в чорний колір, половину в білий і встановимо фотоелемент. На його виході буде в половині випадків 0, а в половині 1 (тобто ми вимірюємо кут з точністю до 180 градусів).

Розгортка барабана:

Зробивши поруч іншу доріжку з двох чорних і білих частин і поставивши другий фотоелемент, одержуємо можливість виміряти кут з точністю до 90 градусів:

Зробивши третю,

ми виміряємо кут з точністю до 45 градусів і т. д. Ця ідея має, однак, недолік: у момент перетинання границь відразу кілька фотоелементів змінюють сигнал, і якщо ці зміни відбудуться не одночасно, на якийсь час показання фотоелементів будуть безглуздими. Коди Грея дозволяють уникнути цієї небезпеки. Зробимо так, щоб на кожному кроці змінювалося показання лише одного фотоелемента (у тому числі й на останньому, після цілого оберту).

Написана нами формула дозволяє легко перетворити дані від фотоелементів на двійковий код кута повороту.

Задача 2. Надрукувати всі перестановки чисел 1 ... n так, щоб кожна наступна виходила з попередньою перестановкою (транспозицією) двох сусідніх чисел. Наприклад, при n = 3 допустимим є такий порядок:

3.2 1 - > 2 3.1 -> 2.1 3 - > 1 2.3 - > 1.3 2 - > 3 1 2 (між числами, що переставляються, вставлені крапки).

Розв’язання. Поряд з множиною перестановок розглянемо множину послідовностей

у [ 1 ] ...у [ n ] цілих невід’ємних чисел, в яких у [ 1 ] < = 0,…, у [ n ] < n – 1. У ній стільки ж елементів, скільки в множині всіх перестановок, і ми зараз установимо між ними взаємно однозначну відповідність — кожній перестановці поставимо у відповідність послідовність у [ 1 ] < = 0,…, у [ n ] < = n – 1, де у [ i ] — кількість чисел, менших за і і розташованих ліворуч від і у цій перестановці. Взаємна однозначність випливає з такого зауваження. Перестановка чисел 1... п виходить із перестановки чисел 1... n - 1 додаванням числа n, яке можна вставити на кожне з n місць. При цьому до послідовності, що зіставляється з нею, додається ще один член, який приймає значення від 0 до n - 1, а попередні члени не змінюються. При цьому виявляється, що зміна на одиницю одного з членів послідовності у відповідає перестановці двох сусідніх чисел, якщо всі наступні числа послідовності у приймають максимально або мінімально можливі для них значення. Саме збільшення y [ і ] на 1 відповідає перестановці числа із його правим сусідом, а зменшення — з лівим.

Тепер пригадаймо розв’язання задачі про перерахування всіх послідовностей, на кожному кроці якого один член змінюється на одиницю. Замінивши прямокутну дошку дошкою у формі сходів (висота і-ої вертикалі дорівнює і) і рухаючи шашки за тими ж правилами, ми перерахуємо всі послідовності у, причому і-й член буде змінюватися, тільки коли всі наступні шашки стоять біля краю. Треба ще вміти паралельно зі зміною у коректувати перестановку.

Очевидний спосіб вимагає відшукання в пій числа і; це можна полегшити, якщо крім самої перестановки зберігати функцію і | - > позиції числа і в перестановці (зворотне до перестановки відображення) і відповідним чином її коректувати. Ось яка виходить програма:

Задачі з обробки масивів і матриць

Задача 1. Знайти середнє арифметичне загальної сукупності елементів тих рядків заданої матриці, останній елемент яких дорівнює 1.

Задача 2. Одержати масив X(n) за правилом: Хі = 1, якщо в і-му стовпці заданої матриці є хоча б один елемент, що перевищує задане значення С, інакше Хі = 0. Знайти загальну кількість елементів, більших за С.

Задача 3. Дано масив А(5,5). Змінити частину матриці, що знаходиться під головною діагоналлю, у такий спосіб: якщо елемент А [ і, j ] цієї частини матриці більше від елемента А [ j, i ], то задати елементу А [ і, j ] нове значення, що дорівнює напівсумі двох цих елементів.

Задача 4. Визначити найдовшу послідовність розташованих підряд нулів у заданому одномірному масиві.

Задача 5. Написати програму, що зчитує задану кількість одномірних масивів, визначає мінімальний елемент у кожному з них і підраховує кількість нулів серед елементів, розташованих за мінімальним.

Задача 6. Написати програму, що підраховує в кожному з заданих рядків кількість слів «мама».

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

Задача 8. У текстовому файлі відсортувати рядки за зростанням їхніх довжин.

Задача 9. У файлі з матеріальних чисел переставити елементи таким чином, щоб спочатку були записані всі додатні, потім всі від’ємні, а потім всі нулі.

Задача 10. Записати в кінець кожного рядка текстового файлу кількість слів у цьому рядку.









загрузка...

Віртуальна читальня освітніх матеріалів для студентів, вчителів, учнів та батьків.

Наш сайт не претендує на авторство розміщених матеріалів. Ми тільки конвертуємо у зручний формат матеріали з мережі Інтернет які знаходяться у відкритому доступі та надіслані нашими відвідувачами. Якщо ви являєтесь володарем авторського права на будь-який розміщений у нас матеріал і маєте намір видалити його зверніться для узгодження до адміністратора сайту.

Дозволяється копіювати матеріали з обов'язковим гіпертекстовим посилання на сайт, будьте вдячними ми затратили багато зусиль щоб привести інформацію у зручний вигляд.

© 2008-2019 Всі права на дизайн сайту належать С.Є.А.