101 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 618
    • Репутація: 4962

Re: Перевірка впорядкованості елементів одновимірного масиву

ur_naz написав:

скільки варіантів упорядкування може бути взагалі?

У межах заданої задачі, чи взагалі в межах усіх можливих задач?

102 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 601
    • Репутація: 13310

Re: Перевірка впорядкованості елементів одновимірного масиву

Слухайте, не збивайте людину. В умові чітко сказано: "Відповідь сформулювати: «Yes >>» – якщо масив є упорядкованим за зростанням, «Yes <<» – якщо масив є упорядкованим
за спаданням або «No»."
3 варіанти. ТРИ. Ніяких за незростанням і періодичних не треба виявляти.
Раджу завести 2 булеві змінні

bool can_be_sorted_up = true;
bool can_be_sorted_down = true;

Далі в циклі порівнюємо кожен елемент із попереднім і змінюємо на false ту змінну, яка описує ситуацію, що відпала:

if(x[i-1]<=x[i])
    can_be_sorted_down = false;

Ну а в кінці - перевіряєте, якщо одна зі змінних true, то виводите відповідне повідомлення, якщо ж обидві false - тоді No.
Це складно?

Подякували: P.Y.1

koala вебсайт

103 Відповідь від ur_naz

  • ur_naz
  • ur_naz
  • Користувач
  • Поза форумом
  • Дата реєстрації: 19.06.2016
  • Повідомлень: 1 755
    • Репутація: 496

Re: Перевірка впорядкованості елементів одновимірного масиву

koala написав:

3 варіанти. ТРИ

якесь божевілля... то п'ять, то три. це тир, чи шо? чи ви 2 на 2 помножити не вмієте?

104 Відповідь від wander Востаннє редагувалося wander (07.01.2020 23:46:17)

  • wander
  • wander
  • Replace Team
  • Поза форумом
  • Звідки: No-man's land
  • Дата реєстрації: 28.02.2019
  • Повідомлень: 1 277
    • Репутація: 1213

Re: Перевірка впорядкованості елементів одновимірного масиву

Це як у тому анкедоті?
Лише у нас могли вирішення простої задачки розтягнути на 6 сторінок обговорень :D
90% з яких це просто вода.

105 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 601
    • Репутація: 13310

Re: Перевірка впорядкованості елементів одновимірного масиву

ur_naz написав:
koala написав:

3 варіанти. ТРИ

якесь божевілля... то п'ять, то три. це тир, чи шо? чи ви 2 на 2 помножити не вмієте?

Де я писав про 5? Ви наркоман бачите, що в гілці, крім вас та автора, ще є люди? Ви бачите, кому відповідаєте?

adziri написав:

90% з яких це просто вода.

Як і ваш допис.

Akos_Bond, дивіться, в чому проблема з вашою змінною t: по-перше, її назва не дозволяє зрозуміти, що саме вона містить (а містить вона ознаку того, яка це послідовність - у вигляді так само незрозумілих чисел 1,2,3); а по-друге, якщо ми використовуємо одну змінну, то нам складно розібратися, що саме відбувається, бо, як я вже писав раніше, у нас можливі ситуації (масив з 1 елементу), коли масив відсортований І за зростанням, І за спаданням, тобто нам доводиться перебирати всі можливі комбінації в залежності від поточної ситуації (що у вас у коді й відбувається, хоч це й можна спростити). Коли є 2 змінні - одна відстежує, чи відсортована переглянута частина масиву за зростанням, а друга - за спаданням, то все стає значно простіше.

Подякували: P.Y.1

koala вебсайт

106 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 618
    • Репутація: 4962

Re: Перевірка впорядкованості елементів одновимірного масиву

koala написав:

Слухайте, не збивайте людину. В умові чітко сказано: "Відповідь сформулювати: «Yes >>» – якщо масив є упорядкованим за зростанням, «Yes <<» – якщо масив є упорядкованим
за спаданням або «No»."
3 варіанти. ТРИ. Ніяких за незростанням і періодичних не треба виявляти.
Раджу завести 2 булеві змінні

bool can_be_sorted_up = true;
bool can_be_sorted_down = true;

Далі в циклі порівнюємо кожен елемент із попереднім і змінюємо на false ту змінну, яка описує ситуацію, що відпала:

if(x[i-1]<=x[i])
    can_be_sorted_down = false;

Ну а в кінці - перевіряєте, якщо одна зі змінних true, то виводите відповідне повідомлення, якщо ж обидві false - тоді No.
Це складно?

Насправді проблемою є недовизначеність умови: що робити з повторюваними елементами? Наприклад, масив 1 1 2 є неспадним, але чи можна назвати його впорядкованим за зростанням (і, якщо ні, чи можливо його впорядкувати за зростанням по-справжньому? Тільки виключивши повторювані елементи — більш ніяк). На практиці, проте, під «зростанням» часто розуміють неспадання, і в випадку, коли елементи не повторюються, різниця між цими поняттями зникає. Було б, звичайно, добре, якби в умові було сказано, що елементи вхідного масиву не повторюються, або зростання визначалось як неспадання — проте, прямим текстом цього не сказано. Як і не сказано, що масив має містити щонайменше два елементи (інакше послідовність з 1 елемента чи порожня послідовність є в однаковій мірі і впорядкованою, і невпорядкованою).

У випадку, коли вхідний масив не міститиме зростаючих чи спадаючих пар (довжина менше 2, або всі елементи рівні), змінні, що вказують на зростання і спадання, по завершенню перевірки обидві будуть true. Що, фактично, є четвертим випадком. Чи слід такий масив вважати невпорядкованим? Навіть якщо після завершення роботи два true виводитимуть той же результат, що й два false, протягом перевірки різниця між ними зберігається (вже хоча б тому, що початково вони обидві true).

Подякували: leofun011

107 Відповідь від ur_naz

  • ur_naz
  • ur_naz
  • Користувач
  • Поза форумом
  • Дата реєстрації: 19.06.2016
  • Повідомлень: 1 755
    • Репутація: 496

Re: Перевірка впорядкованості елементів одновимірного масиву

P.Y. написав:

масив 1 1 2 є неспадним, але чи можна назвати його впорядкованим за зростанням

так

108 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 601
    • Репутація: 13310

Re: Перевірка впорядкованості елементів одновимірного масиву

P.Y. написав:

Насправді проблемою є недовизначеність умови: що робити з повторюваними елементами? Наприклад, масив 1 1 2 є неспадним, але чи можна назвати його впорядкованим за зростанням

Ні, це зветься "впорядкований за неспаданням".

P.Y. написав:

послідовність з 1 елемента чи порожня послідовність є в однаковій мірі і впорядкованою, і невпорядкованою

Ні, з міркувань узагальнення така послідовність є впорядкованою. У невпорядкованій послідовності можна переставити елементи і зробити її впорядкованою; послідовність з 1 елемента є вже впорядкованою.

P.Y. написав:

по завершенню перевірки обидві будуть true. Що, фактично, є четвертим випадком. Чи слід такий масив вважати невпорядкованим?

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

koala вебсайт

109 Відповідь від ur_naz

  • ur_naz
  • ur_naz
  • Користувач
  • Поза форумом
  • Дата реєстрації: 19.06.2016
  • Повідомлень: 1 755
    • Репутація: 496

Re: Перевірка впорядкованості елементів одновимірного масиву

якщо за не спаданням і за зростанням це є не одне й те ж, то яким чином допоможуть дві змінні?.. ви там визначитеся вже, що й коли ви маєте на увазі...

110 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 601
    • Репутація: 13310

Re: Перевірка впорядкованості елементів одновимірного масиву

ur_naz написав:

якщо за не спаданням і за зростанням це є не одне й те ж, то яким чином допоможуть дві змінні?.. ви там визначитеся вже, що й коли ви маєте на увазі...

Я визначився і написав чіткі визначення. Якщо до вас щось не доходить - то цитуйте конкретні слова і речення, значення яких ви не розумієте.

koala вебсайт

111 Відповідь від ur_naz Востаннє редагувалося ur_naz (08.01.2020 21:26:23)

  • ur_naz
  • ur_naz
  • Користувач
  • Поза форумом
  • Дата реєстрації: 19.06.2016
  • Повідомлень: 1 755
    • Репутація: 496

Re: Перевірка впорядкованості елементів одновимірного масиву

та я вже усе написав, для себе
це ж не я тут шкідливі поради роздаю

112 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 618
    • Репутація: 4962

Re: Перевірка впорядкованості елементів одновимірного масиву

koala написав:

Ні, це зветься "впорядкований за неспаданням".

Тобто, в контексті даної задачі (де визначається впорядкованість лише за зростанням та за спаданням) його слід вважати невпорядкованим? А проте,

koala написав:

У невпорядкованій послідовності можна переставити елементи і зробити її впорядкованою;

Послідовність 1 1 2 жодними перестановками неможливо перетворити на послідовність, де кожен елемент, крім першого, більший за попередній. Щоб ця умова виконувалась, елементи слід не лише переставити, а й виключити зайві. Проте, не всі алгоритми сортування передбачають можливість виключення елементів — якщо відсортувати бульбашковим сортуванням такий масив за зростанням, то яким має бути правильний результат?

113 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 274
    • Репутація: 2720

Re: Перевірка впорядкованості елементів одновимірного масиву

Akos_Bond написав:

Відповідь сформулювати:
«Yes >>» – якщо масив є упорядкованим за зростанням,
«Yes <<» – якщо масив є упорядкованим за спаданням або
«No».".

#include <stdbool.h>
#include <stdio.h>

bool asc (int const l, int const r) { return l <= r; }
bool desc(int const l, int const r) { return l >= r; }

bool is_ordered(
    int const *const arr, int const size,
    bool (*order)(int const, int const)
);

int main(void) {
    int size = 3;
    int *arr = malloc(size * sizeof(int));
    // init
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    // ~
    bool ascend  = is_ordered(arr, size, asc );
    bool descend = is_ordered(arr, size, desc);
    free(arr);
    if(ascend ) printf("Yes >> \r\n");
    if(descend) printf("Yes << \r\n");
    if(!ascend && !descend) printf("No \r\n");
    return 0;
}

bool is_ordered(
    int const *const arr, int const size,
    bool (*order)(int const, int const)
) {
    for(int i = 1; i < size; ++i)
        if(!order(arr[i - 1], arr[i]))
            return false;
    return true;
}
Visual Studio написав:

Build: 1 succeeded, 0 failed

Подякували: koala1

leofun01 вебсайт