Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 161051
21.02.2009, 05:48
0.00 руб.
0 4 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

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

Обсуждение

Неизвестный
21.02.2009, 17:23
общий
это ответ
Здравствуйте, 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;
}
Неизвестный
22.02.2009, 11:23
общий
Пожалуйста, помогите с 1 - ой задачей...
Может решении задачи поможет, я не разобрал...
Решение:
Длинный корень

Для начала найдем количество цифр в ответе. Покажем, что квадрат K-значного числа имеет либо 2*K-1, либо 2*K цифр. Действительно, квадрат наименьшего K-значного числа, т.е. числа 10K-1, равен 102K-2, т.е. имеет 2*K-1 цифру; квадрат наибольшего K-значного числа, т.е. числа 10K-1, равен 102K-2*10K+1, т.е. имеет 2*K цифр. Поскольку функция y=x2 монотонно возрастает для всех x>0(т.е. для любых x1,x2 > 0, таких что x1 < x2 выполнено x12 < x22), квадрат любого K-значного числа будет иметь либо 2*K-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. В стоящей справа сумме все слагаемые, кроме первого, представляют собой частный случай перемножения "длинных" чисел, изложенный выше. А первое слагаемое уже было вычисленно на предыдущем шаге алгоритма.
Неизвестный
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
СПАСИБО!!!
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
23.02.2009, 15:25
общий
Haji Kemal Erimez:
Вам не кажется, что слишком много программ хотите в одном вопросе?
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа