Задача тижня 27.02.12 – 04.03.12

Міжпланетний рейс

У деякій країні проводився відбір учасників першого міжпланетного пасажирського рейсу. Кожному з N кандидатів було надано його унікальний особистий номер (натуральне число від 1 до N). Спеціальна комп’ютерна програма створила список із цих номерів, розташувавши їх у випадковому порядку, і розпочала рахувати їх по колу, починаючи з номера 1. Якщо порядковий номер при рахуванні співпадає із значенням особистого номеру, то відповідний кандидат займає місце в космічному кораблі, а його особистий номер виключається зі списку номерів, і рахування розпочинається заново з наступного номеру в списку. Програма завершує відбір кандидатів, якщо в результаті чергового обходу кола номерів не було відібрано жодного кандидата.

1. Створіть програму знаходження кількості учасників рейсу та їх особистих номерів.

Вхідні дані

Значення N – ціле число від 1 до 100, вводиться з клавіатури або задається як константа.

Вихідні дані (виводяться на екран)

Значення K – кількість учасників першого міжпланетного пасажирського рейсу – космічних туристів;

значення Tj (j = 1, 2, …, К) – перелік особистих номерів цих учасників (туристів) у порядку їх вибору програмою.

2. Заповніть тестову таблицю за результатами роботи програми:

Аналіз розв’язку задачі «Міжпланетний рейс»

Вирішення задачі можна розподілити на декілька кроків.

Крок 1. Заповнюємо масив R натуральними числами від 1 до N, розташувавши їх у випадковому порядку.

Для цього можна спочатку створити масив R[i] = i , де i = 1, 2,…, N, а потім у циклі, наприклад, N разів обміняти місцями два довільно вибраних елемента R[j] та R[k], де значення j, k задаються датчиком випадкових чисел. Проте випадкові числа нерівномірно заповнюватимуть проміжок від 1 до N, і перемішування може виявитися недостатньо ефективним.

Покажемо інший варіант створення масиву R. Спочатку елементам масиву R надаємо нульові значення, що означає “місця вільні”. Послідовно заповнюємо масив значеннями від 1 до N, визначаючи їх місця в масиві за допомогою датчика випадкових чисел. Якщо місце, визначене датчиком, зайняте, зміщуємося в наступне, доки не знайдемо вільного місця.

кінець циклу

Зауважимо, що для тестування розробленої програми значення елементів масиву R слід буде вводити з клавіатури або з файлу.

Крок 2. Потрібно знайти позицію елемента (змінна i) зі значенням 1.

кінець циклу

Знайдене значення визначає той номер i елемента масиву R, з якого розпочинається рахування.

Крок 3.

Введемо змінні: K – кількість туристів на борту, T – масив з їх особистими номерами;

m – індекс кандидата в масиві R, з якого починаємо чергове рахування кандидатів.

p – змінна, що відповідає порядковому номеру кандидата у процесі рахування.

Якщо у процесі рахування черговий елемент масиву є таким, що R[i] = p (порядковий і особистий номери збігаються), то збільшуємо кількість K туристів на 1, переносимо значення R[i] (або p) у масив T (тобто T[K] = p), елемент R[i] “забираємо” з масиву (надаємо йому нульового значення (R[i] = 0), його індекс запам’ятовуємо (m = i) і розпочинаємо рахування знову (p = 1) з наступного елемента масиву (i = i +1).

Якщо черговий елемент масиву R[i] дорівнює нулю, значення p не змінюємо і продовжуємо перегляд елементів масиву R.

Перегляд завершується, якщо всі кандидати стали туристами (K = N) або чергове значення індексу масиву співпадає з індексом останнього вибраного туриста (i = m) (це означає, що весь список переглянуто, коло замкнулося, а жодного кандидата не переведено в туристи).

Цілком доцільно перегляд масиву організувати в циклі з постумовою (повторювати…до).

до (i =m) OR (K = N);

Таблиця за результатами роботи програми:

Журі оцінило надіслані розв’язки наступним чином: