Доброго дня, шановні гості і друзі!
Під час своєї педагогічної праці з дітьми я помітив, що кожен з нас по різному мислить і по різному приходить до своєї істини. Тут Ви знайдете мої авторські розв'язки задач з програмування. Можливо, вони Вам допоможуть знайти свій шлях до розв'язку. Я, вчитель який навчається, тому не можу Вам сказати, що мої розв'язки оптимальні. Сайт буду поповнювати поступово, оскільки це клопітка праця.
Задачі для початківців NetOi
Задача Newcircle
Дано послідовність цілих чисел. Відрізок послідовності утворюють числа, що йдуть в послідовності підряд в порядку зростання. Знайти номери чисел, якими починається і закінчується перший відрізок з максимальною сумою, а також цю суму.
Технічні умови. Програма читає спочатку кількість елементів послідовності, а потім саму цю послідовність. Всі числа в одному рядку, їх розділено пропусками. Гарантовано, що послідовність не порожня, і всі розрахунки можна вести в межах типу longint. Програма виводить в один рядок 3 числа через пропуск - номера першого і останнього елемента шуканого відрізка і суму чисел відрізку.
Приклади
Введення 3 -2 -1 0
Виведення 3 3 0
Введення 5 1 2 -3 3 0
Виведення 1 2 3
Опишемо спочатку змінні, які будемо використовувати для розв'язку даної задачі.
n - кількість елементів в послідовності.
int a[1000] - масив, я якому буде власне зберігатися послідовність, яку введе користувач, і в якому ми будемо шукати послідовність чисел, які йдуть послідовно і мають максимальну суму.
i,j - лічильники, які будуть використовуватися в циклах.
imin,imax - змінні, які будуть зберігати номера першого і останнього елемента відрізка з максимальною сумою.
sum - змінна, яка буде зберігати суму елементів даного відрізка, якщо його елементи додатні.
max - змінна, яка буде зберігати максимальну суму серед пройдених відрізків.
count_poz - змінна, яка буде зберігати кількість додатних чисел, що ввійшли до останнього відрізку, вона необхідна, для знаходження номеру першого елемента imin шуканого відрізка.
1. Вводимо змінну n.
2. Введення масиву.
3. Обнулення змінних sum,i,count_poz.
4. Організація циклу while. Вихід з циклу буде відбуватися по умові i<n-1. i - це лічильник, який в циклі буде змінюватися і через який ми будемо мати доступ до елементів масиву. В мові Сі номери елементів масиву починаються з 0, тому в умові циклу ми поставили i<n-1. Тому що в тілі циклу буде перевірятися чи виконується умова рівності попередній елемент збільшений на 1 рівний наступному елементу. Тобто, чи йде зростання чисел і чи йдуть вони послідовно. Якщо ми дійдемо до елементу n-1 і почнемо перевіряти цю умову. То попередній елемент - це буде елемент n-1, а наступний елемент - це буде елемент n. І ми вийдемо за межі масиву, що призведе до критичної помилки. Тому в умові циклу стоїть перевірка i<n-1, а не i<n, яка часто використовується в схожих задачах.
5. В тілі циклу перевіряємо умову if(a[i]+1==a[i+1]), тобто чи попередній елемент збільшений на 1, дорівнює наступному елементу. Тобто, чи йде зростання послідовних чисел. Наприклад, така послідовність:
| a[0] | a[1] | a[2] |
| -1 | 0 | 1 |
Якщо ця умова виконується, то:
5.1. То ми знайшли початок впорядкованої зростаючої послідовності. Потрібно її пройти і знайти максимальну суму цієї послідовності. Проходити будемо її за допомогою циклу while. В якому використаємо лічильник j. Початкове значення лічильника буде дорівнювати поточному значенню змінної i. Тобто, j=i. А саме початку впорядкованої зростаючої послідовності.
5.2. Використовуємо цикл while з наступною умовою (a[j]+1==a[j+1])&&(j<n-1). Це звучить так: поки поточний елемент збільшений на 1, дорівнює наступному елементу, тобто поки елементи послідовності впорядковані і зростають, і поки ми не дійшли до кінця масиву.
5.2.1. В тілі циклу перевіряємо, чи поточний елемент a[j]<0, якщо так, то перевіряємо чи він більший за змінну max. Якщо він більший за max, то max=a[j], тобто елемент a[j] є поки що максимальною сумою даної послідовності. Оскільки послідовність складається з одного елемента і його номер j, то imin=j;imax=j;.
5.2.2. Інакше, якщо цей елемент додатній, то додаємо a[j] до змінної sum. І змінну count_poz збільшуємо на один. Тоді, в кінці циклу ми будемо знати скільки додатних елементів ми додали до змінної sum. І зможемо визначити початок і кінець послідовності з максимальною сумою
5.2.3. Збільшуємо змінну j на 1. Для того щоб перейти до перевірки наступного елемента.
5.3. Після того, як ми вийшли з циклу перевіряємо, чи ми не дійшли до кінця масиву. Тобто, j==n-1. Якщо це так:
5.3.1 То перевіряємо, чи останній елемент менший нуля. Якщо він менший нуля, то він і є максимальною сумою останньої впорядкованої зростаючої послідовності. Тоді, max=a[j];imin=j;imax=j;.
5.3.2. Інакше, якщо останній елемент додатній, то додаємо його до змінної sum. При цьому цей раз змінну count_poz збільшувати на один не будемо, оскільки під час обрахунку початкового елементу послідовності з максимальною сумою буде включено один зайвий елемент. Перевіряємо, чи змінна sum більша за max. Якщо це так, то max=sum. Номер кінцевого елемента з максимальною сумою буде поточний елемент j, тому imax=j. А для підрахунку початкового елементу, ми від змінної j віднімемо кількість додатних елементів, які ми додавали до sum. Тобто, imin=j-count_poz. Чому ми один раз не збільшували змінну count_poz. Уявимо, що була зростаюча впорядкована послідовність, в якій додатні числа мали в масиві номера 5,6,7. Виходить, що додатних чисел 3, номер останнього елементу 7. Це означає, що номер першого елементу 7-3=4. Але насправді номер першого елемента має значення на 1 більше і це 5. Щоб уникнути такого неправильного підрахунку ми один раз змінну count_poz не збільшуємо. Після того, як ми зробили дані операції обнуляємо змінну sum і змінну count_poz, для того щоб при наступному пошуку ми не отримали не вірне значення sum і кількості додатних елементів в певній зростаючій впорядкованій послідовності нашого масиву.
5.3.3. Оскільки ми у внутрішньому циклі дійшли до останнього елементу масиву необхідно організувати вихід з основного циклу, який ми почали у пункті 4. Тому змінній i присваюємо значення i==n-1 і умова i<n-1 уже дасть результат false.
5.4. Інакше, якщо ми не дійшли до кінця масиву і вийшли коли закінчилася на даному етапі певна впорядкована зростаюча послідовність. То:
5.4.1. Перевіряємо, чи останній елемент на якому впорядкована зростаюча послідовність закінчилась a[j]<0. Якщо так, то він і є максимальною сумою цієї послідовності і тоді перевіряємо чи a[j]>max. Якщо це так, то max=a[j];imin=j;imax=j;.
5.4.2. Інакше, до змінної sum додаємо останній елемент a[j] на якому ми зупинилися в циклі. Знову змінну count_poz не збільшуємо на 1. Перевіряємо чи sum>max. Якщо це так. То, знову: max=sum;imax=j;imin=j-count_poz;. Обнуляємо змінні sum та count_poz.
5.4.3 У внутрішньому циклі ми не дійшли до останнього елементу в нашому масиві можуть бути ще послідовності, які відповідають нашій умові, щоб зовнішній цикл не починав пошук з самого початку ми змінимо змінну i. Для цього ми їй присвоюємо значення на один більше чим змінна j, на якій ми зупинилися. Тобто, i=j+1. Наприклад, в нас є наступний масив -2 -1 0 1 2 0 -1 3 4. Внутрішній цикл зупиниться коли j=4. Пам'ятаємо, що в Сі нумерація з нуля. Тоді пошук наступної послідовності ми почнемо з 5 елементу. Тому i=j+1, і пошук в зовнішньому циклі продовжиться.
6. Якщо умова в пункті 5 не виконалася, то це означає, або послідовність далі спадна, або наступний елемент, такий самий як попередній, або різниця між ними не рівна 1. Тоді в такому випадку, поточний елемент масиву є також послідовністю, що відповідає нашій умові, але вона складається з одного елементу. Тоді перевіряємо чи a[i]>max. Якщо ця умова виконується, то max=a[i];imin=i;imax=i;. Збільшуємо змінну i на 1, для того щоб перейти до перевірки наступного елементу масиву з допомогою зовнішнього циклу.
7. Виводимо на екран змінні imin,imax,max.
Задача Circle
Василько взяв великого циркуля та зайшов до кімнати, підлога якої являє собою квадрат зі стороною рівною M(M>1м). Поставивши циркуль на перетині діагоналей цього квадрата він почав будувати кола. Перше коло мало діаметр 10 см., друге – 30, трете – 40, четверте – 60, п’яте – 70, шосте – 90 см. і т.д. Скільки повних кіл може побудувати в цій кімнаті Василько?
Технічні умови. Програма зчитує з клавіатури ціле число M – довжину стіни кімнати в сантиметрах. Програма виводить на екран одне ціле число – кількість повних кіл, які можна тут побудувати.
Приклади
Введення 240
Виведення 16
Введення 380
Виведення 25
M - змінна, яка буде зберігати розмір сторони квадрата
i - змінна, яка буде лічильником в циклі while і буде зберігати діаметр поточного кола, який побудував хлопчик.
n - змінна, яка буде лічильником в циклі while і буде зберігати кількість побудованих хлопчиком кіл
1. Описуємо змінні M,i,n.
2. Вводимо змінну M.
3. Присвоїмо початкове значення змінної i=10, оскільки перше коло мало діаметр 10см. Значення змінної n=0, оскільки кількість кіл які побудував хлопчик буде підраховуватися в циклі. Поки ми ще нічого не підраховували, тому кількість кіл 0.
4. Починаємо цикл whilе з наступною умовою i<=M. Тобто, поки діаметр кола меньший за сторону квадрата. Чому так, давайте глянемо на малюнок:
Як видно з малюнку, коло буде тільки тоді влазити в квадрат, коли його діаметр менший за сторону квадрата.
4.1. Якщо умова циклу виконалася, то поточне коло влізло в квадрат і ми збільшуємо змінну n на 1. Тобто, n++
4.2. З умови видно, що хлопчик один раз збільшує коло на 10, а наступного разу збільшує коло на 20, і так повторює до тих пір, поки він не намалює коло, яке не влазить в квадрат. Для того, щоб знати на скільки збільшувати діаметр кола на 10 чи на 20 ми скористаємося змінною n. Якщо кількість кіл, які побудував хлопчик парна, то потрібно збільшити діаметр наступного кола на 10, в іншому випадку збільшити його на 20. Після цієї провірки цикл while закриваємо.
4.(Коментарь). Підсумуємо як працює цикл. Спочатку провіряється умова циклу чи поточне коло влазить в квадрат. Якщо ми зайшли в цикл. То збільшуємо кількість кіл на 1. Далі перевіряємо парність змінної n з допомогою оператора if. Якщо змінна n парна, то збільшуємо змінну i на 10, інакше збільшуємо її на 20. Повертаємося до перевірки умови циклу.
5. Після циклу виводимо на екран значення змінної n. Тобто, кількість кіл, які побудував хлопчик.
Немає коментарів:
Дописати коментар