1

Тема: Застосування АТД " СПИСОК " до розв’язання прикладних задач на C++

Написати програму роботи з довгими числами (довгі числа – це числа, що виходять за діапазон допустимих значень будь-якого стандартного цілого або дійсного типу). Структура збереження довгих чисел повинна забезпечувати ефективну роботу з довільними (додатними і від’ємними) довгими цілими числами. Реалізувати роботу з довгими числами:

Обчислення  значення n!, де n > 12.
Допоможіть будь ласка.В кого які є ідеї як можна виконати цю задачу?Дякую!

2

Re: Застосування АТД " СПИСОК " до розв’язання прикладних задач на C++

Спершу потрібно вияснити, чи можна використовувати готову структуру "Список", чи потрібно її реалізувати самостійно. В будь-якому випадку потрібно написати метод (функцію) множення списку на ціле число.
Ідея така: в списку в кожному елементі буде міститися одна цифра (ефективніше, звичайно, буде використовувати стільки цифр, скільки дозволяє тип елементів списку. Але для простішого розуміння нехай буде одна). Список складається із елементів типу byte (чи що є подібне в вашій версії C++). Множення реалізуємо подібно до того, як в молодшій школі множили в стовпчик.
Наприклад, нехай в списку записане число 24 (тобто елементи 4 і 2) і його треба перемножити на 5. Множимо 4*5=20. Останню цифру, тобто 0 залишаємо першій комірці, а 2 переносимо в другу. Другу комірку рахуємо 2*5+2=12. В другій комірці зберігаємо 2, створюємо новий елемент списку і поміщаємо туди 1. Тобто 120 буде записане, як список з елементів 0, 2, 1.
Ще потрібно буде реалізувати виведення списку на екран.

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

3

Re: Застосування АТД " СПИСОК " до розв’язання прикладних задач на C++

Я б реалізовував множення в стовпчик на рядках. Це не сильно гірше за ефективністю від BCD, віджирає всього лише вдвічі більше пам'яті, а працювати з ними - звичніше.

4

Re: Застосування АТД " СПИСОК " до розв’язання прикладних задач на C++

yooll підказав ідею у вірному напрямі. Єдине - я би використав вектор замість списку, щоб спростити і розуміння, і здійснення операцій (індекс цифри відповідав би її розряду). Вийшло би щось типу:

typedef char digit; // Назвемо так, щоб зекономити пам'ять: цифра в одному байті вміститься цілком.
struct LongNumber
{
    vector<digit> digits;
    void parseFromText(string input);
    const string toString()const;
//...Реалізація...
};

bunyk, ідея цікава. А як бачите логіку реалізації?