консультация онлайн № 161051: здрасти помогите решить задачи с помощью длинной арифметикой №1: длинный корень по заданному натуральному числу а требуется найти на

Родились сегодня:
Иван Васильевич

Модератор

pocketmonster

2-й класс

Алексеев Владимир Николаевич

Мастер-Эксперт

Magic2hand

Студент

Sergey V. Gornostaev

Советник

epimkin

Профессионал

Hunter7007

Мастер-Эксперт

Мы ВКонтакте

8.14.10

27.06.2022

JS: 2.15.10
CSS: 4.9.15
jQuery: 3.6.0

jQuery

jQuery UI

Bootstrap
Font Awesome

наверх

CradleA (Мастер-Эксперт)
Администратор раздела
С / С++

Программирование Компьютеры Операционные системы Мобильные телефоны

Создание программ на языках C и C++.

Больше

Уважаемый пользователь!

Задавая вопрос в рассылку по C / C++, для быстрого получения ответа соблюдайте ряд несложных для исполнения требований:
1. Несмотря на то, что C и C++ являются кроссплатформенными языками программирования, в ряде случаев (например, при необходимости создать приложение с графическим интерфейсом пользователя либо с использованием системных API) эксперту может понадобиться знание целевой операционной системы. Поэтому в тех случаях, когда для Вас это имеет значение, указывайте её в тексте вопроса. В случае если Вы этого не сделали и не ответили на уточняющие вопросы в мини-форуме, по умолчанию администратор рассылки будет считать, что Вы работаете с Windows XP.

2. Если для Вас требуется создать приложение с использованием какого-то определённого набора инструментов, то указывайте его в вопросе (компилятор, интегрированная среда разработки, библиотека классов для построения графического интерфейса пользователя и т.п.). При этом не используйте русскую транслитерацию названия среды разработки / компилятора / библиотеки. Указывайте название программного продукта, с которым работаете, полностью с приведением номера его версии. Microsoft Visual C++ 6 и Microsoft Visual C++ 2008 Express Edition, Borland C++ 5.02 и Borland C++ Builder 6.0, Turbo C++ 3.1 и Turbo C++ 2006 Explorer - совсем не одно и то же. В случае если Вы этого не сделали и не ответили на уточняющие вопросы в мини-форуме, по умолчанию администратор рассылки будет считать, что Вы работаете со средой Microcoft Visual Studio 2005

3. Повторю, что в случае, если имеется необходимость создать графическое (оконное) приложение, указывайте, с помощью каких инструментов оно должно быть создано: GTK, Qt, API Вашей операционной системы, MFC, VCL, Windows Forms и т.д. и т.п. В случае если Вы этого не сделали и не ответили на уточняющие вопросы в мини-форуме, по умолчанию администратор рассылки будет считать, что для создания графического интерфейса пользователя Вы используете MFC.

4. Не пытайтесь связываться с экспертами и администратором по внутреннему пейджеру портала: этим Вы лишь замедляете решение Вашей задачи, т.к. все уточнения, связанные с Вашей задачей, тем самым доступны лишь Вашему корреспонденту, но не другим экспертам. Для переписки по любым проблемам, связанным с Вашим вопросом, используйте его мини-форум.

5. Не пытайтесь задавать всё новые и новые вопросы (имеются в виду просьбы решить новые задачи, не имеющие отношения к прежней) в мини-форуме вопроса, на который уже было дано решение. Также не задавайте несколько не связанных между собой вопросов в одной форме: администратор рассылки оставляет за собой право удалять лишние вопросы на своё усмотрение.

6. Администратор рассылки оставляет за собой право удалять вопросы, связанные с программированием на C / C++ лишь косвенно, если на них не поступило ответов в течение 5 дней.

Удачи!

Консультация онлайн # 161051

Раздел: С / С++
Автор вопроса: Haji Kemal Erimez
Дата: 21.02.2009, 05:48 Консультация неактивна
Поступило ответов: 1

Здрасти!
Помогите решить задачи с помощью длинной арифметикой...

№1:
Длинный корень

По заданному натуральному числу А требуется найти наибольшее число В такое, что B2 <= A.

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

Во входном файле INPUT.TXT записано натуральное число A (A <= 103000).

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

В выходной файл OUTPUT.TXT выведите максимальное натуральное число B, квадрат которого не превосходит A. Число B следует выводить без лидирующих нулей.
Примеры:
input.txt: 17
output.txt: 4

№2:
Больше-меньше - 2

Программист Билл занимается разработкой программного обеспечения для новейшего робота-исследователя, которого учёные планируют отправить на Марс с целью поиска там следов разумной жизни. Модули, которые отвечают за передвижение робота и сбор проб грунта, Билл уже скачал из Интернета. Оставалось лишь научить робота отличать разумные формы жизни от неразумных. Для этого Боб несколько месяцев посещал программистские форумы, и, наконец, нашёл подходящий модуль. Теперь, чтобы определить, является ли тот или иной объект представителем внеземной расы, роботу достаточно сравнить два вещественных числа.

Однако за несколько часов до запуска корабля на Марс обнаружилось, что робот неправильно сравнивает вещественные числа! Чтобы исправить эту ошибку, учёные обратились за помощью к Вам.

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

Входной файл INPUT.TXT состоит из двух строк, в каждой из которых записано по одному вещественному числу без ведущих нулей. Целая и дробная части отделяются точкой, которая может быть опущена, если число целое. Каждое из чисел содержит не более 10000 цифр.

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

В выходной файл OUTPUT.TXT выведите один символ ‘<’, если первое число меньше второго, ‘>’, если больше, и ‘=’, если числа равны.

Примеры:
1.
input.txt:
2.39
3.61
output.txt: <
2.
input.txt:
123
12.3
output.txt: >
3.
input.txt:
12345678
12345678.0
output.txt: =
4.
input.txt:
-1.0
1.0
output.txt: <

№3:

Сумма факториалов

Факториалом натурального числа K называется произведение K!=1×2×3×…×K.

Требуется написать программу, которая по заданному числу N вычислит сумму 1!+2!+…+N! .

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

Входной файл INPUT.TXT содержит одно натуральное число N (N ≤ 200).

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

Выходной файл OUTPUT.TXT должен содержать все десятичные знаки искомой суммы.

Примеры:
1. input.txt: 1
output.txt: 1
2. input.txt: 2
output.txt: 3
3. input.txt: 3
output.txt: 9

№4:

Длинное произведение
(Время: 1 сек. Память: 16 Мб Сложность: 46%)

Даны целые неотрицательные числа M и N. Требуется найти произведение этих чисел.

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

Входной файл INPUT.TXT содержит в первой строке число M, а во второй строке – число N. (0 <= M, N <=10 в степени 2500)

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

В выходной файл OUTPUT.TXT выведите произведение чисел M и N.

Примеры:
1.
input.txt:
5
7
output.txt: 35
2.
input.txt:
4134937827592
784
output.txt: 3241791256832128
3.
input.txt:
9876543210
1023456789
output.txt: 10108215200126352690

Заранее СПАСИБО! smile

Ответ # 1, Micren (Посетитель)

Здравствуйте, Haji Kemal Erimez!
Решение 2й задачи

Приложение:
#include <fstream> #include <string> using namespace std; class real { private: string whole; string fract; friend istream& operator>>(istream& stream,real& r); friend char compare(const real& r1,const real& r2); }; istream& operator>>(istream& stream,real& r) { string str; stream>>str; if(!stream.fail()) { int index=str.find('.'); r.whole=str.substr(0,index); if(index!=string::npos) r.fract=str.substr(index+1); for(index=r.fract.length()-1;index>-1&&r.fract[index]=='0';index--); r.fract.erase(index+1); if(!r.whole.length()||r.whole[0]!='-') r.whole='+'+r.whole; } return stream; } char ans(bool positive,char ch) { if(!positive) { switch(ch) { case '>':return '<'; case '<':return '>'; } } return ch; } char compare(const real& r1,const real& r2) { int len1_w=r1.whole.length(), len2_w=r2.whole.length(); if(r1.whole[0]!=r2.whole[0]) return r1.whole[0]=='+'?'>':'<'; bool p=r1.whole[0]=='+'; if(len1_w==len2_w) { for(int i=0;i<len1_w;i++) { if(r1.whole[i]>r2.whole[i])return ans(p,'>'); else if(r1.whole[i]<r2.whole[i])return ans(p,'<'); } int len1_f=r1.fract.length(), len2_f=r2.fract.length(); int minlen=min(len1_f,len2_f); for(int i=0;i<minlen;i++) { if(r1.fract[i]>r2.fract[i])return ans(p,'>'); else if(r1.fract[i]<r2.fract[i])return ans(p,'<'); } return (len1_f==len2_f)?'=':(len1_f>len2_f)?ans(p,'>'):ans(p,'<'); } else return (len1_w>len2_w)?ans(p,'>'):ans(p,'<'); } int main() { real r1,r2; ifstream in("INPUT.TXT"); ofstream out("OUTPUT.TXT"); in>>r1>>r2; out<<compare(r1,r2); return 0; }

Micren

Посетитель

21.02.2009, 17:23

Нет оценки ответа

наверх

Мини-форум консультации # 161051

неизвестный 177315	= общий = 22.02.2009, 11:23 Пожалуйста, помогите с 1 - ой задачей... Может решении задачи поможет, я не разобрал... Решение: Длинный корень Для начала найдем количество цифр в ответе. Покажем, что квадрат K-значного числа имеет либо 2K-1, либо 2K цифр. Действительно, квадрат наименьшего K-значного числа, т.е. числа 10K-1, равен 102K-2, т.е. имеет 2K-1 цифру; квадрат наибольшего K-значного числа, т.е. числа 10K-1, равен 102K-210K+1, т.е. имеет 2K цифр. Поскольку функция y=x2 монотонно возрастает для всех x>0(т.е. для любых x1,x2 > 0, таких что x1 < x2 выполнено x12 < x22), квадрат любого K-значного числа будет иметь либо 2K-1, либо 2*K цифр. Следовательно, если число A из входного файла имеет N цифр, то корень из него будет иметь ровно (N+1) div 2 цифр. Теперь, когда мы знаем количество цифр в числе, будем последовательно подбирать его цифры, начиная со старших. Пусть K старших цифр уже подобраны. Поставим на K+1 место самую большую цифру - 9, и будем уменьшать ее до тех пор, пока квадрат полученного таким образом числа (считая, что все цифры ответа, начиная с K+2 и до самой младшей равны 0) не станет меньше либо равен числу A из входного файла. Таким образом, мы подобрали K+1 цифру нашего числа. Продолжая этот процесс, получим ответ на поставленную задачу. В изложенном решении используется операция умножения "длинных" чисел. Благодаря алгоритму умножения "в столбик" эта задача сводится к многократному умножению "длинных" чисел на "короткие" и сложению "длинных" чисел. Заметим, что эта операция легко выполняется в том случае, если одно из чисел является степенью 10, умноженной на "короткое" число. Тогда достаточно умножить "длинное" число на это короткое, а затем сдвинуть результат на нужное число позиций, что равносильно умножению числа на степень 10. Пусть aK - число, полученное на K-м шаге нашего приближения, b - очередная цифра, умноженная на 10 в соответствующей степени. Тогда aK+12=(aK+b)2=aK2+2aKb+b2. В стоящей справа сумме все слагаемые, кроме первого, представляют собой частный случай перемножения "длинных" чисел, изложенный выше. А первое слагаемое уже было вычисленно на предыдущем шаге алгоритма.
неизвестный 177316	= общий = 22.02.2009, 11:28 И помогите решить пожалуйста задачу по комбинаторике: Игра с монеткой Петя играет в интересную игру. Для этой игры необходима монетка. Петя подбрасывает ее n раз и считает, сколько раз выпадает «решка». Если решка выпадает хотя бы m раз, то Петя считает, что он выиграл игру. Однажды Петя задумался, какова вероятность того, что он выиграет игру. Для этого он хочет найти количество последовательностей результатов подбрасывания монетки, содержащих ровно n подбрасываний, при которых «решка» выпала хотя бы m раз. Помогите Пете — найдите это число, считая, что при каждом броске монетка может выпасть либо «орлом», либо «решкой». Входные данные Входной файл INPUT.TXT содержит два целых числа: n и m (1 < n <= 20, 0 <= m <= n). Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. примеры: 1. input.txt: 2 0 output.txt: 4 2. input.txt: 3 2 output.txt: 4 СПАСИБО!!!
Лысков Игорь Витальевич Советник ID: 7438 177473	= общий = 23.02.2009, 15:25 Haji Kemal Erimez: Вам не кажется, что слишком много программ хотите в одном вопросе? ===== "Если вы заметили, что вы на стороне большинства, — это верный признак того, что пора меняться." Марк Твен

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

наверх

Лидеры

CradleA (Мастер-Эксперт)

С / С++

Консультация онлайн # 161051

Ответ # 1, Micren (Посетитель)

Micren

Посетитель

21.02.2009, 17:23

Мини-форум консультации # 161051

Лысков Игорь Витальевич