Дана перестановочка ось такого виду. 4n, 4n-4. 8,4, 4n-1. 4n - 5. 7, 3, 4n-2. 4n-6. 6,2,4n-3,4n-7. 5,1.
Треба знайти формулу обчислення числа інверсій
Це завдання з заліку. НЕ ЗДАТИ алгебру. тим більше залік - ШОК) (ну я люблю математику. і сам її іноді почитую у вільний час)
Ось як я робив це завдання на заліку, я знайшов формулу - число інверсій = 5 * n * n + n
Ось мій хід міркування:
Число інверсій дорівнює сумі числа інверсій для кожного елемента послідовності!
Спочатку розглядаємо (ну я так вирішив) найбільші члени цієї послідовності йдуть. як би поспіль - по спадаючій. тобто розглядаємо:
4n. 4n-1, 4n -2,4n-3 - Бачимо що число інверсій даної послідовності - є арифметична прогресія. у якій перший член = 0. останній = 3. різницю між елементами = 1, а число елементів завжди 4!
Далі ми знову починаємо розглядати спадаючу послідовність членів перестановки. менших 4n-3. ну тобто 4n-4. 4 n-7. якщо розглядати тільки лише її - то висновок робимо такий же як і в попередньому розгляді - число інверсій = 6. однак, тепер ці члени перестановки. ще треба порівнювати і з тими - що я розглянув вище. і зробивши це розгляд приходимо до висновку. що тепер початковий член прогресії збільшується на 1. а число інверсій для кожного наступного члена послідовності збільшується на 2. тобто як би маємо 1. 3. 5 7 + число інверсій розглянуте вище (тобто 6). Поміркувавши пару хвилин в голові і виходячи з нашої перестановки робимо висновок. що при числі елементів рівним наприклад 3. ми до попереднього значення додаватимемо тугіше суму арифметичної прогресії. перший член у якій вже не 1. а 2. а всі інші збільшуються на 3 та тка далі. одним словом отримуємо суму арифметичних прогресій. в яких перший член завжди = 0 а для кожної наступної збільшується на 1. число елементів завжди в кожній по 4. а різниця між елементами збільшується на 1. склавши формулу суми цих прогресій я і отримав вона буде = 5 * n * n + n
Скажіть будь ласка шановні знавці в чому я не правий. і можливо це завдання треба було вирішувати зовсім по іншому. І якщо так. то як. А то перездача на носі. і якщо я цього не розумію. то всі мої плани - коту під хвіст
На плечах гігантів, на спинах електронів
Відповідь вірний.
Можна було б розглянути всього чотири арифметичні прогресії з різницею d = 4 і першими членами, відповідно, 4n, 4n-1, 4n-2 і 4n-3 - було б менше обчислень.
Але відповідь такий же виходить.
Так. але питання. як треба було вирішувати. так що б препод у мене прийняв це завдання.
На плечах гігантів, на спинах електронів
Ви його вже здали?
Тоді чекайте вердикту.
Вирішувати можна як завгодно, лише б правильно.
Якщо ви нормально обгрунтували свої міркування, а не писали щось типу цього:
Поміркувавши пару хвилин в голові і виходячи з нашої перестановки робимо висновок. що при числі елементів рівним до прикладу 3.
то ваше рішення цілком вірне.
Дилетант. у мене ряд 2 6 7 5 1 3 4 число інверсій 12?
На плечах гігантів, на спинах електронів
Пошук по спільноті