Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 24.07.2015
Сообщений: 7

Длинная арифметика

26.09.2015, 22:53. Показов 2227. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вот условие задачи:
Кликните здесь для просмотра всего текста
Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:

1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.

2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).

3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.

4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на n-ом шаге.

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.

Входные данные

Первая строка содержит количество этапов эволюции n(1 ≤n ≤ 100), которые произошли на планете Олимпия до текущего времени. Вторая и третья строки содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.

Выходные данные

Вывести одно натуральное число - номер ближайшего предка для двух видов.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
Sample 1
4
15
12

Sample 2
18
233016
233008
Выходные данные
Sample 1
3

Sample 2
14563


Мое решение:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <string>
 
using namespace std;
 
const int MAX=260000; ///максимальное количество цифр в числе
 
class longint ///класс длинных чисел
{
public:
    int arr[MAX]; ///число в виде массива
    int sz; ///количество значимых цифр числа
public:
    longint() { for(int i=0; i<MAX; i++) arr[i]=0; }
    ///вроде и не нужно обнуление. Пусть будет, скорости хватает
    bool operator==(longint& li2)
    {
        for (int i=0; i<MAX; i++)
            if (arr[i]!=li2.arr[i]) return false;
        return true;
    }
    bool operator!=(longint& li2)
    {
        return !(*this==li2);
    }
    bool operator>(longint& li2)
    {
        for (int i=0; i<MAX; i++)
            if(arr[i]!=li2.arr[i])
                return arr[i]>li2.arr[i];
    }
    void in() ///ввод
    {
        string s; cin >> s;
        sz=s.length();
        for (int i=MAX-sz; i<MAX; i++)
            arr[i]=s[i-(MAX-sz)]-48;
    }
    ///можно было прегрузить операторы перенаправления
    ///не стал заморачиваться, вывод в консоль подходит
    void out() ///вывод
    {
        for (int i=MAX-sz; i<MAX; i++)
            cerr << arr[i];
    }
    void div2() ///деление на два
    {
        int ost=0, sztemp=0;
        ///если число начинается с 1, то его количество знаков
        ///уменьшится после деления на два
        if(arr[MAX-sz]==1) sztemp++; ///Вот тут быдлокод, знаю
        for(int i=MAX-sz; i<MAX; i++)
        {
            ost=ost*10+arr[i];
            arr[i]=ost/2;
            ost=ost%2;
        }
        sz-=sztemp; ///и тут
    }
};
 
int main()
{
    longint li1, li2;
    int dummy; cin >> dummy; ///UNNECESSARY LOL
    li1.in(); li2.in();
    while (li1!=li2)
    {
        if (li1>li2) li1.div2();
        else li2.div2();
    }
    li1.out();
    return 0;
}

Все непонятное откомментил, вот тут для непонятливых нашел объяснение алгоритма:
https://www.google.com.ua/url?... eA&cad=rjt
Это прямая ссылка на скачивание файла, на странице 5 решение.
Как мне кажется, программа работает. К сожалению, не проходит ни одного теста. Пожалуйста, помогите
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.09.2015, 22:53
Ответы с готовыми решениями:

Длинная арифметика
http://www.acmp.ru/index.asp?main=task&amp;id_task=103 Как решить эту задачу? С помощью чего, и в чем смысл решения длянной...

Длинная арифметика
Ребята,объясните как решить задачу , напишите хоть часть кода. Пусть даны числа a , b . Найти a+b, если a и b не больше чем 10 в...

Длинная арифметика
Нужно написать программу которая полностью выводит число 2^-200. (желательно с комментариями, для понимания)

2
Эксперт PHP
 Аватар для Kerry_Jr
3106 / 2591 / 1219
Регистрация: 14.05.2014
Сообщений: 7,236
Записей в блоге: 1
26.09.2015, 23:04
Цитата Сообщение от nikitosoleil Посмотреть сообщение
C++
1
cerr << arr[i];
т.е. Вы реально считаете, что нужно использовать не стандартный поток вывода, а стандартный поток ошибок?
0
0 / 0 / 0
Регистрация: 24.07.2015
Сообщений: 7
26.09.2015, 23:14  [ТС]
Kerry_Jr, однако! Огромное спасибо. Я дурак. Это оставалось со времен дебага. Думал, что вывод в консоль циферок он не может быть каким-то особым, не понимал, что отсутствие буферизации (какие там особенности сerr?) при выводе может не понравится системе. Максимальный балл
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
26.09.2015, 23:14
Помогаю со студенческими работами здесь

Длинная арифметика
:senor: Здраствуйте, пишу модуль длинной математики. В принципе, работоспособность у него положительная. Но в силу моей неопытности меня...

Длинная арифметика: найти остаток от деления большого числа (до 10^100 000) на 12
Здравствуйте, вопрос по поводу задачки, хочу попытаться реализовать решение на плюсах, а не на питоне. Суть такая: надо найти остаток от...

длинная арифметика
Долгое время бьюсь как составить программу по этой теме в интернете искал нашел это for (int i=(int)s.length(); i&gt;0; i-=9) if (i...

Длинная арифметика
Как сделать типы длинных чисел, например, знаковое 256-ти битное целое и 256-ти битное вещественное с 224-х битной мантиссой и 32-х битным...

Длинная арифметика
Программка уже почти готова, единственное неправильно находит остаток при делении По заданию: Надо ввести 2-ва целых числа неогран....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru