предлагаю нескалько задачек проверим навыки???

← →
gn (2003-07-15 13:52) [0]

Задача 1.

Число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить делится ли число на 15.
Задача 2.
Дано число в K-ичной системе счисления
an an-1 ...a0 (K<=36).
Найти остаток от деления его на m.
Числа K, n, m, как и остаток от деления на m, представляются в десятичной системе счисления.

Задача 3.

Любое натуральное число N можно единственным способом представить с помощью некоторых целых неотрицательных d[0], ... , d[s] в виде

N=d[s]*(s+1)!+d[s-1]*s! +...+d[1]*2!+d[0] (*)

при условии, что 0<=d[i]<=i+1, i=0,..,s, где d[s]<>0.

Дано s+1 натуральное число d[0], ..., d[s], и натуральное K, s<200,d[i]<65535, K<65535. Найти остаток от деления числа N, определяемого в факториальной системе (*) числами d[0], ..., d[s], на число K.

Задача 4.

Числа Фибоначчи U[1], U[2], ... определяются начальными значениями U[1]=1, U[2]=2 и соотношением

U[N+1] = U[N] + U[N-1].

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Даны две строки, представляющие числа A и B. Найти строку, представляющую число A+B.

Пример. Исходные строки "10101" и "100" представляют числа 8+3+1=12 и 3. Ответом является строка "100010", представляющая строку 13+2=15=12+3.

Примечание. Строки могут быть столь длинны, что числа A и B превысят максимально допустимое в вашем компьютере целое число.

Задача 5.

Сосчитать количество единиц в двоичной записи числа i.

Задача 6.

Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.

0 -> 01 -> 0112 -> 01121220 ->...

Составить алгоритм, который по введенному N, (0<=N<=3000000000) определяет, какое число стоит на N-ом месте в последовательности.

gn
cn 1101

← →
gn (2003-07-15 13:53) [1]

Задача 7.

Дан массив X(100) и Y(100). Записать алгоритм, меняющий последовательно местами значения элементов X(k) и Y(k) для этих таблиц, для k=1,2,...,100, не используя промежуточных переменных.

Задача 8.

Точки с целочисленными координатами из 1-го квадранта помечаются числами 0,1,2,... слева направо и снизу вверх таким образом, что очередной точке приписывается минимальное число, отсутствующее в вертикали и горизонтали, проходящей через точку. Первой помечается точка (0,0).

Написать программу, которая

1. По заданным координатам x и y, x>=0, y>=0, x,y- целые, определяет пометку точки.

2. По заданной координате x и пометке точки y, x>=0, y>=0, x, y - целые, определяет вторую координату точки.

Задача 10.

Известно, что запись числа A в позиционных системах счисления с основанием p и q имеет вид бесконечной периодической дроби с периодом 2:

A = O,(ab) = O,(ba) (*)

где a и b - различные цифры в этих системах счисления.

Написать программу, которая для введенных натуральных чисел p и q (2<=p,q<=30, p>q) находит и выводит все возможные пары значений цифр a и b, удовлетворяющих соотношению (*). Если таковых нет, вывести сообщение "Пригодных цифр нет".

Предусмотреть защиту от ввода ошибочных данных.

Примечание: Значением числа, запись которого в позиционной системе счисления с основанием S есть 0, cdef (где c,d,e,f - цифры), являются

Задача 11.

Определим множества K[i] рекуррентно. Пусть K[0] = [0,1]. Разделим сегмент [0,1] на три части точками 1/3 и 2/3 и удалим из него интервал (1/3,2/3). Получим множество K[1], состоящее из двух оставшихся сегментов [0,1/3] и [2/3,1]. Каждый из них разделим на три части (точками 1/9 и 2/9 для первого сегмента, и точками 7/9 и 8/9 - для второго ) и удалим средние интервалы (1/9,2/9) и (7/9,8/9). Таким образом получаем множество K[2], и т.д. Пусть мы построим множество K[i]. Поделим каждый оставшийся сегмент из K[i] на 3 части и удалим из этих сегментов средние интервалы. Получим, таким образом, из K[i] множество K[i+1].

Вводятся 3 целых числа n,a,b.

Необходимо определить, принадлежит ли точка с координатой a/b множеству K[n].

gn
cn 1101

← →
gn (2003-07-15 13:54) [2]

Задача 12.

Дано натуральное n. Подсчитать количество решений неравенства x*x + y*y<n в натуральных (неотрицательных целых) числах, не используя действий с вещественными числами. Количество операций должно быть порядка (n1/2)

Задача 13.

Число называется совершенным, если оно равно сумме всех своих делителей за исключением его самого. Любое четное совершенное число представимо в виде

2p-1 * (2p - 1), где р натуральное число.

Найти двоичное представление для максимального совершенного четного числа меньшего введенного N.

Задача 14.

Заданы натуральные числа E,K,M,T в записи химической реакции

ХеАk + Y -> YmAt + X,

где A,X,Y - атомы или группы атомов. Написать алгоритм, который находит такие натуральные коэффициенты, чтобы знак "стрелки" можно было заменить знаком равенства.

Задача 15.

Вводятся целые числа a и b. Пусть у треугольника ABC координаты A=(0,0), B=(a,b), а обе координаты C=(x,y) - целые числа, и площадь треугольника ABC не равна нулю.

Какую минимальную площадь может иметь треугольник ABC?

Задача 16.

Имеется N банок с целочисленными объемами V1, ..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды.

Задача 17.

Функция f с натуральными аргументами и значениями определена так: f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1) = f(n) + f(n+1). Составить программу вычисления f (n) по заданному n, требующую порядка log n операций

Задача 18.

Вывести на экран число 2n, n<=10000, n - натуральное.

Задача 19.

Определить количество повторений каждой из цифр 0,1,2,...,9 в числе NN (N в степени N), N <= 1000.

gn
cn 1101

← →
gn (2003-07-15 13:54) [3]

Задача 21.

Вводится N. Необходимо найти, на сколько нулей оканчивается N!=1*2*3*...*N.

<Задача 22.

На входе программе даются два числа N и P. Программа на выходе должна дать такое максимальное число M, что N! делится на P в степени M, но не делится на P в степени M+1.

Примечание.

1.Числа N и P так велики , что нет смысла считать значение N!.

2.Числа N и P являются натуральными.

Задача 23.

Натуральное число N>1 представить в виде суммы натуральных чисел так, чтобы произведение этих слагаемых было максимально.

Задача 24.

Задается любое положительное действительное число R. Найти положительные действительные R1,R2,...,Rn, Ri<4 ,i=1,...,n, такие, что R=R1*R2*...*Rn=R1+R2+...+Rn

Задача 25.

Даны целые числа А(0),А(1),...,А(5). Найти множество корней уравнения

А(5)*X5 + А(4)*X4 + ... + А(0) = 0,

если известно, что все корни - целые числа, A(0)<>0.

Задача 26.

Вывести в порядке возрастания все обыкновенные несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают 15. Массив при этом заводить не следует.

<Задача 27.

Дан многогранник, в вершинах которого записаны целые числа.

Одним ходом можно выбрать одно ребро, и к числу, записанному в одном из его концов прибавить один, а из числа, записанного в другом конце - вычесть 1.

Какому необходимому и достаточному условию должны удовлетворять записанные числа, чтобы с помощью таких ходов можно было добиться, чтобы во всех вершинах был одновременно записан ноль? Ответ обосновать.

Задача 28.

a). Полином

p(x)=A[n]*xn+A[n-1]*xn-1+ ... +A[1]*x+A[0]

задается своими коэффициентами A[n], ... ,A[0]. Найти его значение P в точке x.

b). Число в k-ичной системе задается своим представлением (A[n], ... ,A[0]),т.е. в десятичной системе оно имеет значение

A[n]*kn+A[n-1]*kn-1+ ... +A[1]*k+A[0].

Найти это значение.

Задача 29.

Полином N-ой степени

задается своими коэффициентами a[i]. Найти коэффициенты b[i],i=0,...,n*m, m-ой степени полинома A(x). Числа n,m<=40.

Задача 30.

Вычислить коэффициенты A[1], A[2], ..., A[N] многочлена

P(x) =xn + A[1]*xn-1+...+ A[N-1]*x + A[N]

с заданными действительными корнями X[1], X[2], ..., X[N].

Задача 31.

Многочлен

задается набором своих коэффициентов a[i], i=0,..,n. Необходимо вычислить коэффициенты b[i] такого многочлена, что

для заданного d.

Задача 32.

Вычислить значение полинома

f(x)=ax4+bx3+cx2+dx+e

для x=1, ..., 10000, используя не более 51000 операций *,+.

gn
cn 1101

← →
` frizZ. ` (2003-07-15 14:28) [4]

Ты ИЗДЕВАЕШСЯ ???

← →
gn (2003-07-15 14:30) [5]

` frizZ. `
не вкоем случае
просто мне очень понравилась идея юрия зотова вот я и решил проверить способности форумчан.

gn
cn 1101

← →
Fredericco (2003-07-15 14:33) [6]

Из-за тебя нас уволят с работы :-)

← →
gn (2003-07-15 14:40) [7]

Fredericco ©
почему???

gn
cn 1101

← →
sniknik (2003-07-15 14:41) [8]

тут даже сайт был с такими проверками...

признайся, таким хитрым способом хочеш экзамен по информатике сдать?

← →
gn (2003-07-15 14:44) [9]

sniknik ©
нет что ты я решил почти все
немного времени не хватает
думаю сегодня вечером по решаю ещё работа личная жизнь и кореша много времени отнимают но ведь и не отдыхать нельзя . верно??

gn
cn 1101

← →
Fredericco (2003-07-15 14:47) [10]

gn ©
Да вместо того, что бы работать - сижу и решаю :-))))

← →
gn (2003-07-15 14:49) [11]

Fredericco ©
прости я знаюь вещь заразная
но ведь не только интересная но и полезная

gn
cn 1101

← →
Sha (2003-07-15 15:28) [12]

gn © (15.07.03 14:44)
а что решить не удалось?

← →
Soft (2003-07-15 15:46) [13]

http://www.certifications.ru/testselection.php

← →
MBo (2003-07-15 16:35) [14]

32:
var n,i:integer; c:array[0..4] of integer; reslt:Int64; d1,d2,d3,d4:integer; begin n:=20; c[0]:=3; c[1]:=2; c[2]:=5; c[3]:=-3; c[4]:=4; for i:=1 to n do begin Reslt:=c[0]+i*(c[1]+i*(c[2]+i*(c[3]+i*c[4]))); Memo1.Lines.Add(Format("%d %d",[i,reslt])); end; //Схема Горнера //4 + и 4 * на каждый аргумент Memo1.Lines.Add(""); reslt:=c[0]; d1:=c[1]+c[2]+c[3]+c[4]; d2:=14*c[4]+6*c[3]+2*c[2]; d3:=36*c[4]+6*c[3]; d4:=24*c[4]; for i:=1 to n do begin Reslt:=reslt+d1; d1:=d1+d2; d2:=d2+d3; d3:=d3+d4; Memo1.Lines.Add(Format("%d %d",[i,reslt])); end; //4 сложения, умножений нет вообще!

← →
Юрий Зотов (2003-07-15 17:17) [15]

Особенно понравилась задача 31.

← →
_Nicola_ (2003-07-15 17:51) [16]

Задача 18 тоже прикольная.

← →
CinCinNut (2003-07-15 18:03) [17]

> Юрий Зотов © (15.07.03 17:17)

что-то я не понял, похоже условие не полное?

← →
Юрий Зотов (2003-07-15 18:40) [18]

> CinCinNut © (15.07.03 18:03)

Конечно.

← →
Igor__ (2003-07-15 19:08) [19]

> Задача 32.
>
> Вычислить значение полинома
>
> f(x)=ax4+bx3+cx2+dx+e
>
> для x=1, ..., 10000, используя не более 51000 операций *,+.

Ну это не серезно

f(x)=ax4+bx3+cx2+dx+e=x(a4+b3+c2+d)+e;

k:=a*4+b*3+c*2+d;

for x:=1 to 10000 do
memo1.lines.add(intToStr(x*k+e));

Итого 3 умножения и 3 сложения при подготовке
10000 умножений и 10000 сложений при роботе:))))

> Задача 5.
>
> Сосчитать количество единиц в двоичной записи числа i.

i:=0;
while n>0 do
begin
if n mod 2=1 then inc(i);
n:=n div 2;
end;

:)))))))))))))

> Задача 7.
>
> Дан массив X(100) и Y(100). Записать алгоритм, меняющий
> последовательно местами значения элементов X(k) и Y(k) для
> этих таблиц, для k=1,2,...,100, не используя промежуточных
> переменных.

for i:=1 to 100 do
begin
x[i]:=x[i]+y[i];
y[i]:=x[i]-y[i];
x[i]:=x[i]-y[i];
end;

Если не ошибаюсь.

> Задача 11.
>
> Определим множества K[i] рекуррентно. Пусть K[0] = [0,1].
> Разделим сегмент [0,1] на три части точками 1/3 и 2/3 и
> удалим из него интервал (1/3,2/3). Получим множество K[1],
> состоящее из двух оставшихся сегментов [0,1/3] и [2/3,1].
> Каждый из них разделим на три части (точками 1/9 и 2/9 для
> первого сегмента, и точками 7/9 и 8/9 - для второго ) и
> удалим средние интервалы (1/9,2/9) и (7/9,8/9). Таким образом
> получаем множество K[2], и т.д. Пусть мы построим множество
> K[i]. Поделим каждый оставшийся сегмент из K[i] на 3 части
> и удалим из этих сегментов средние интервалы. Получим, таким
> образом, из K[i] множество K[i+1].
>
> Вводятся 3 целых числа n,a,b.
>
> Необходимо определить, принадлежит ли точка с координатой
> a/b множеству K[n].

Где ограничения???
А вообще облом писать.
Делим k[0] на три части смотрим какой части пренадлежит a/b. Продолжаем данную процедуру до того времени пока не дойдем до n.

> Задача 12.
>
> Дано натуральное n. Подсчитать количество решений неравенства
> x*x + y*y<n в натуральных (неотрицательных целых) числах,
> не используя действий с вещественными числами. Количество
> операций должно быть порядка (n1/2)

count:=0;
for i:=0 to n div 2 do
begin
count:=count+trunc(sqrt(n-x*x));
end;
поидее должно роботать.

← →
Igor__ (2003-07-15 19:33) [20]

> Задача 13.
>
> Число называется совершенным, если оно равно сумме всех
> своих делителей за исключением его самого. Любое четное
> совершенное число представимо в виде
>
> 2p-1 * (2p - 1), где р натуральное число.
>
> Найти двоичное представление для максимального совершенного
> четного числа меньшего введенного N.

2p-1 * (2p - 1) - зачем дужку умножать на еденицу - проверь формулу.

> Задача 15.
>
> Вводятся целые числа a и b. Пусть у треугольника ABC координаты
> A=(0,0), B=(a,b), а обе координаты C=(x,y) - целые числа,
> и площадь треугольника ABC не равна нулю.
>
> Какую минимальную площадь может иметь треугольник ABC?

(x,y) должны быть максимально близкими к центру отрезка АВ -> нуно перебрать все ближайшие вершины и выбрать нужную площадь.(это не претедирует на правильность)

> Задача 18.
>
> Вывести на экран число 2n, n<=10000, n - натуральное.

Наверное самая трудная задача :)))))))

Дальше нужно думать:))))))

Да, кстати, у меня в теори программирования БООЛЬШАЯ ДЫРА - динамическое программирование. Подскажите чо-нибуть толковое.

← →
NikotiN (2003-07-15 20:07) [21]

номер 4. Вроде даже работает!

program Project2;
{$APPTYPE CONSOLE}
type
TPoint=record
x,y:longint;
end;
TA=array of byte;

function GetFib(num:longint):TPoint;
var a:TPoint;
b:integer;
begin
if num =0 then
begin
getfib.x:=1; getfib.y:=1; exit;
end;
if num =1 then
begin
getfib.x:=1; getfib.y:=1; exit;
end;
if num>2 then
begin
a:=GetFib(num-1);
getfib.y:=a.x; getFib.x:=a.x+a.y;
end
else
begin
getfib.x:=2; getFib.y:=1;
end;
end;

function Solve(Bin:string): longint;
var b,s:string;
rez:longint;
begin
b:=bin; rez:=0;
while length(b)>=1 do
begin
s:=copy(b,0,1); delete(b,1,1);
if s="1" then rez:=rez+getfib(length(b)+1).x;
end;
Solve:=rez;
end;

function Check(a:ta;int:longint):boolean;
var rez:longint;
i:integer;
f,r:boolean;
begin
r:=FALSE;
rez:=0;
for i:=0 to high(a) do
begin
if a[i]=1 then rez:=rez+getfib(i+1).x;
end;
f:=TRUE;
for i:=0 to high(a)-1 do
if (a[i]=1) and(a[i+1]=1) then
f:=false;
if f and(rez=int) then r:=TRUE;
Check:=r;
end;

function Solve2(int:longint):string;
var
a:TA;
i,j,k:integer;
f:boolean;
begin
setlength(a,1);
a[0]:=0;
f:=true;
while f do
begin
inc(a[0]); i:=0;
while a[i]=2 do
begin
if high(a)<i+1 then
begin
setlength(a,i+2); a[i+1]:=0;
end;
inc(a[i+1]); a[i]:=0; inc(i);
end;
if check(a,int) then f:=FALSE;
end;
for k:=high(a) downto 0 do write(a[k]);
end;

var a, b:longint;
s1,s2:string;

begin
readln(s1); readln(s2);
a:=Solve(s1); b:=solve(s2);
solve2(a+b);
readln;
end.

← →
sergey2 (2003-07-15 20:15) [22]

21
ИМХО самая простая задача

Что-то типа этого:
k:=int(n/5);

Не помню как целая часть на дельфи. Но вобщем вы поняли...

← →
Marser (2003-07-15 20:19) [23]

Так, gn, признавайся откуда достал (а то мне понравилось :-) )?

← →
sergey2 (2003-07-15 20:20) [24]

Извиняюсь... Ошибся... Просто сходу написал, почти не вникая.

← →
Igor__ (2003-07-15 20:38) [25]

> sergey2

Для меня все те что я написал тоже очень лехкие :))))))))
Но все же почему n/5. Откуда это.

Да, что никто ничто не знает про динамическое программирование. Ну продилитесь же инфой.

← →
SergP (2003-07-15 23:12) [26]

> Igor__ © (15.07.03 20:38)
>
> > sergey2
>
> Для меня все те что я написал тоже очень лехкие :))))))))
> Но все же почему n/5. Откуда это.
>
>
> Да, что никто ничто не знает про динамическое программирование.
> Ну продилитесь же инфой.

Вобщем немного ступил я в первый раз (sergey2 - это я)

Правильно будет так:

function KolichestvoNuley(const n:integer):integer;
begin
result:=0;
while n>4 do
begin
n:=int(n/5);
result:=result+n;
end;
end;

а n/5 - потому что если считать кол. нулей то нужно считать сколько раз число делиться на 10, а для этого достаточно посчитать сколько раз оно делиться на 5 (так как 10=5*2, а число двоек явно превосходит число пятерок (если разложить результат на множители) - это очевидно) 1
1*2*3*4 не заканчивается на 0, а вот 1*2*3*4*5 заканчивается, причем через каждые 5 чисел число нулей в результате увеличивается на 1. Кроме того через каждые 25 оно увеличивается дополнительно на 1, и т.д. (5,25,625...5^x)

← →
gn (2003-07-16 06:28) [27]

господа я немогу передать словами свою радость
однако не плохие результаты

Sha © (15.07.03 15:28)
gn © (15.07.03 14:44)
а что решить не удалось?

нет почему доришал

gn
cn 1101

← →
Rouse_ (2003-07-16 06:50) [28]

Мдяяяя Крановщик сидел в башне крана....

← →
SergP (2003-07-16 08:38) [29]

1

Что значит "Число вводится своим двоичным представлением"?
Вобщем я исхожу из предположения что у меня есть функция f[i] возвращающая i-й разряд числа начиная от младшего, и length - разрядность числа:

function IsDiv15(var length:integer):boolean;
var z,k:byte;
begin
z:=0;
k:=1;
for i:=1 to length do
begin
if f[i]=1 then z:=z+k;
if z>=15 then z:=z-15;
k:=k*2;
if k>=16 then k:=1;
end;
result:=(z=0);
end;

← →
SergP (2003-07-16 08:48) [30]

2 gn
лучше скажи что ты не решил, а то неинтерестно решать то что кто-то уже решил...

← →
MBo (2003-07-16 09:03) [31]

>Задача 15.
>Какую минимальную площадь может иметь треугольник ABC?

обозначим координаты xb,yb,xc,yc
Все числа целые, первые два известны.
Длина AB=lc=Sqrt(xb^2+xc^2)

проведем аффинное преобразование - поворот треугольника так, чтобы точка B легла на ось X - угол поворота равен -FiB, где FiB - угол между OX и точкой B.
sin(FiB)=yb/lc
cos(FiB)=xb/lc

B" имеет коорд. lc,0
C" имеет Y координату
yc"=-xc*sin(-FiB)+yc*cos(-FiB)=(xc*yb+yc*xb)/lc

S=1/2*lc*yc"=1/2*(xc*yb+yc*xb)

задача свелась к нахождению пары целых xc,yc, дающих минимальное положительное значение S - диофантово неравенство
Очевидно, выражение в скобках целое=> мин. значение его=1

xc*yb+yc*xb=1
методы решения диофантовых уравнений с использованием НОД известны. Решений бесконечное количество.

← →
gn (2003-07-16 09:05) [32]

← →
MBo (2003-07-16 09:13) [33]

← →
gn (2003-07-16 09:28) [34]

MBo ©
не дружище так не интересно я же не для галочки вот у меня есть решение я хочу сам. надеюсь ты понимаеш о чём я.

gn
cn 1101

← →
sergey2 (2003-07-16 17:35) [35]

> MBo © (16.07.03 09:13)
> >gn ©
> решение 32 выше смотри

Имхо не подходит по условию. 4 * и 4 + это итого 8
а так как чисел 10000 то в итоге получаем 80000, а нужно уложиться в 51000

← →
MBo (2003-07-16 17:44) [36]

>sergey2
2-й способ смотри.
Первый-то хорошо известен, я его для примера привел.

← →
sergey2 (2003-07-16 17:45) [37]

Насчет 32 Есть мысль как уменьшить до около 60000 (но чтобы до 51000 пока не могу придумать)

← →
MBo (2003-07-16 17:55) [38]

>sergey2
посмотрел второй мой способ?
40000

← →
sergey2 (2003-07-16 17:57) [39]

> MBo © (16.07.03 17:44)
> >sergey2
> 2-й способ смотри.
> Первый-то хорошо известен, я его для примера привел.

Понял. Как раз понял как решать и тут твою месагу увидел.
Как-то в первый раз я ее не заметил... :)

← →
MBo (2003-07-17 07:21) [40]

>MBo © (16.07.03 09:03)
поправка
уравнение
xc*yb+yc*xb=NMin
имеет решения при NMin=НОД(xb,yb), т.е.
мин. площадь 1/2, если только xb и yb взаимно просты,
а в общем случае НОД(xb,yb)/2

предлагаю нескалько задачек проверим навыки??? Найти похожие ветки