Пятничные задачки для программистов.

← →
MBo © (2006-04-21 08:55) [0]

1. Дано число N 1..10000. Найти минимальное натуральное число, десятичная
запись которого содержит только нули и единицы, делящееся на N.
Примеры 3 -> 111, 2 -> 10.
Числа могут быть очень длинными, так что для полноценной программной
реализации понадобится кое-какая длинная арифметика, но устроит и принципиальное
решение.

2. Написать функцию f, для данного числа N возвращающую, сколько
единиц встречается в последовательности 1..N.
Например, f(13)=6 [1,2,3,4,5,6,7,8,9,10,11,12,13]

3. Дан массив целых (в т.ч. и отрицательных) чисел.
Найти непрерывный подмассив с наибольшей суммой, и как можно лучшей
асимптотикой алгоритма. Пример [7, -3, 5, -1] -> 0..2 элементы с суммой 9

4. Найти максимальное число, меньшее данного, и состоящее из того же набора
цифр. Пример 321 - 312

5. Дан массив целых (в т.ч. и отрицательных) чисел.
Найти, существует ли в нем непрерывный подмассив с суммой N.
Пример [2 -1 3 5] N=4 -> да, 0..2 N=6 -> нет

6. (Несложная, учебная)
Последовательность многочленов Gi(x) определяется следующим образом :
G0(x) = 1
G1(x) = x - 1
Gk(x) = (x-2*k+1)*G[k-1](x) - (k-1)*(k-1)*G[k-2](x)
Написать программу для вычисления коэффициентов многочлена Gn(x),где n<20

7. ИМХО, непростая, но интересная ;)
Дана последовательность чисел А1...Аn, имеется размер окна m<n
Окно скользит по последовательности с шагом 1, и
на каждом шаге надо найти максимальный элемент, попавший в окно.
Сложность требуется лучше, чем O(n*m)

8. Хитрый интерлейсинг:
Есть три байта R,G,B.
младший бит обозначим как нулевой, старший как седьмой.
побитовая запись этих трех переменных будет выглядеть как
r7,r6,r5,r4,r3,r2,r1,r0
g7,g6,g5,g4,g3,g2,g1,g0
b7,b6,b5,b4,b3,b2,b1,b0

Как быстрее всего, и использовав разумное количество памяти построить
беззнаковое 24битное "число" вида
r7,g7,b7,r6,g6,b6,r5,g5,b5....r0,g0,b0 ?

← →
TUser © (2006-04-21 09:16) [1]

{ 4. Найти максимальное число, меньшее данного, и состоящее из того же набора цифр. Пример 321 - 312 } program Max; {$apptype console} uses SysUtils; function GetLess (Num: string; i: integer; var j: integer): boolean; var k: integer; t: char; begin result := false; t:=Num[i]; for k:=i+1 to length (Num) do begin if Num[k] < t then begin j:=k; result := true; end; end; end; procedure Swap (var Num: string; i, j: integer); var t: char; begin t:=Num[i]; Num[i] := Num[j]; Num[j] := t; end; var Num: string; i,j: integer; begin try Num := ParamStr(1); i := StrToInt (Num); if i <= 0 then raise Exception.Create(""); for i:=length (Num) downto 1 do begin if GetLess (Num, i, j) then begin Swap (Num, i, j); writeln (Num); Halt (0); end; end; writeln ("It""s a minimal number"); except writeln; writeln ("Usage: Max <number>"); end; end.

← →
TUser © (2006-04-21 09:17) [2]

Еще - какие ограничения по скорости/памяти? Например, в 5 - квадратичный алгоритм годится?

← →
TUser © (2006-04-21 09:21) [3]

> 7. ИМХО, непростая, но интересная ;)

Видать, не понял чего-то. В такой формулировке - например, хранить дерево из элементов, находящшихся в окне. Добавлени, удаление, поиск - log(m). Соотв. сложность - n*log (m).

← →
MBo © (2006-04-21 09:53) [4]

>TUser © (21.04.06 09:21) [3]
> 7. Соотв. сложность - n*log (m).
А может, и O(n) можно придумать?

>в 5 - квадратичный алгоритм годится?
Это хороший вариант (поскольку лобовое решение - кубическое), но можно быстрее.

← →
Kaban (2006-04-21 09:58) [5]

а про дракона решили?

← →
alles © (2006-04-21 09:59) [6]

2:

procedure TForm1.Button1Click(Sender: TObject);
function RetNumberOfOne(Number:Integer):integer;
var s:String;
i:integer;
begin
S:=IntToStr(Number);
Result:=0;
for i:=1 to Length(s) do
if (S[i]="1") then Inc(Result);
end;
var total_1, Num,i:integer;
begin
total_1:=0;
Num:=StrToInt(Edit1.Text);
for i:=0 to Num do
total_1:=total_1+RetNumberOfOne(i);
ShowMessage(IntToStr(total_1));
end;

← →
MBo © (2006-04-21 10:08) [7]

>TUser © (21.04.06 09:16) [1]

Для 43578 твой алгоритм дает 34578, а правильно 38754

>Kaban (21.04.06 09:58) [5]
>а про дракона решили?

нет. ветку ту поднял, пока не пропала
http://delphimaster.net/view/15-1144404805/

>alles © (21.04.06 09:59) [6] 2:
Так, конечно, работает, но любопытно было бы обойтись без полного перебора...

← →
default © (2006-04-21 10:17) [8]

1.
послед-ть 1 mod N=1, 10 mod N, 100 mod N, 1000 mod N, ... периодична,
причём период всегда начинается с 1
цель состоит в поиске таких элементов вышеуказанной послед-ти остатков которые в сумме дали бы число нацело делящееся на N, причём ещё нужно гарантировать, чтобы самый дальний от начала элемент послед-ти находится как можно ближе к началу этой послед-ти
она достигается перебором

или нужно ещё думать над оптимальностью перебора?

← →
default © (2006-04-21 10:39) [9]

+[8]
случай N=1 исключён как трюизм;)

← →
MBo © (2006-04-21 13:28) [10]

>default © (21.04.06 10:17) [8]
Честно говоря, не понял :(

← →
default © (2006-04-21 13:29) [11]

2.
код не буду писать, он вопрос технический
интересна идея
поясню на примере
допустим имеем мы число N=43852
узнаем сколько единиц имеют первые 39999 чисел
считать единицы будем так: узнаем сколько чисел имеют единицу в младшем разрядке(нулевом), первом разряде, ..., четвёртом разряде и сложим полученные числа - они и дадут искомое число единиц в 39999(идея поразрядного подсчёта!)
число чисел с единицей в нулевом разряде будет: 10*10*10*4=4000
число чисел с единицей в первом разряде будет: 10*10*10*4=4000
число чисел с единицей в втором разряде будет: 10*10*10*4=4000
число чисел с единицей в третьем разряде будет: 10*10*10*4=4000
число чисел с единицей в четвёртом разряде будет: 10*10*10*10=10000
итого: 4000+4000+4000+4000+10000=26000
итак число единиц в первых 39999 чисел есть 26000
в числе 40000 нет единиц, очевидно
теперь, очевидно, нужно узнать сколько единиц в первых 3852 числах
результат решения всей задачи будет 26000 + число единиц в первых 3852 числах
как, видим мы пришли к той же задаче только при этом избавившись от старшего разряда(идея редукции размерности числа!)
работаем также с числом N=3852
и тд до победного конца

← →
default © (2006-04-21 13:49) [12]

MBo © (21.04.06 13:28) [10]
я описал общую идею
например, для N=7
1 mod 7= 1 (такой остаток будет давать каждый седьмой[так как длина периода у нас получилась 6] единичный разряд начиная с 0-го)
10 mod 7= 3(такой остаток будет давать каждый седьмой единичный разряд начиная с 1-го) и тд
100 mod 7 = 2
1000 mod 7 = 6
10000 mod 7 = 4
100000 mod 7 = 5
1000000 mod 7 = 1
...
то есть имеем последовательность остатков
1,3,2,6,4,5,1,3,2,...

например, для числа 10110=10000 + 100 + 10 его остаток от деления на 7 будет равен остатку от деления на семь суммы (10000 mod 7)+(100 mod 7)+(10 mod 7) и если эта сумма кратна 7, то и число 10110 будет кратна 7
сумму же можно подобрать по разному, например, взять
остатками 4+3=7 и взять числом 10010
но это просто условие получения чисел нужной кратности
минимальное из возможных чисел можно найти перебором

← →
MBo © (2006-04-21 14:11) [13]

>default © (21.04.06 13:49) [12]
Таким образом, мы должны из набора R[i] остатков получить сумму N таким образом, чтобы минимизировать iMax и т.д., например, для N=7 это будет 1+6, т.е. 1001. Это работает, но для больших N мы получим ряд из N остатков, и получается, как мне кажется, что-то типа задачи о рюкзаке, имеющей факториальную сложность (здесь, возможно, будет поменьше, но все равно неслабо). Впрочем, способ, который мне известен, похож на твой и тем же недостатком для больших N страдает.

← →
vovnuke © (2006-04-21 14:21) [14]

1.) "в лоб" (перебор второго множителя с проверкой результата), не устраивает?

← →
MBo © (2006-04-21 14:26) [15]

>vovnuke © (21.04.06 14:21) [14]
Для больших N придется перебирать ОЧЕНЬ большие числа, состоящие из 1 и 0 (порядка N цифр), и делить на N. В длинной арифметике это доооолго...

← →
vovnuke © (2006-04-21 14:27) [16]

нет я предлагаю подбирать второй сомножитель начиная с 2 и пока в результате не получится число состоящее из 1 и 0.

← →
TUser © (2006-04-21 14:37) [17]

> vovnuke © (21.04.06 14:21) [14] [Новое
>сообщение][Ответить]
> 1.) "в лоб" (перебор второго множителя с проверкой
>результата), не устраивает?
>
>
>vovnuke
>
> 1.) "в лоб" (перебор второго множителя с проверкой
> результата), не устраивает?MBo © (21.04.06 14:26)
>[15] [Новое сообщение][Ответить]
>>vovnuke © (21.04.06 14:21) [14]
> Для больших N придется перебирать ОЧЕНЬ большие числа,
> состоящие из 1 и 0 (порядка N цифр), и делить на N. В
> длинной арифметике это доооолго...

Просматриваем двоичные числа от 1 до 2 ** length(N). Для каждого значащего нуля имеем девять (все кроме 1) возможностей. Кол-во чисел определяется умножением. Проблема с числами, длина которых равна длине N - надо обязательно определять, что они больше или меньше. Тут приходится для каждого разряда думать - может ли тут стоять такая или другая циферька. А это некрасиво. Лучше ничего не придемалось.

← →
default © (2006-04-21 14:53) [18]

MBo © (21.04.06 14:11) [13]
я тоже так думаю(про факт-ую сложность)
2 задача как? такое у вас решение?

← →
default © (2006-04-27 18:01) [19]

3 решена(линейное время)
кстати, на этом форуме она вроде раньше проскальзывала, но вроде правильную программу задачи никто не мог объяснить, хотя вообщем теория довольно простая

← →
Cash © (2006-04-27 20:40) [20]

8:
Нам надо расфасовать биты по их местам.
Результат будем записывать в Res: DWord;
Данные будем брать из R, G и B типа Byte.
Иделать будем так:

Res:=0; i:=0; while i < 8 do begin if boolean(B shr i) then Res:=Res+Trunc(Power(2,i*3)); if boolean(G shr i) then Res:=Res+Trunc(Power(2,i*3+1)); if boolean(R shr i) then Res:=Res+Trunc(Power(2,i*3+2)); inc(i); end;

Получаем последовательность вида "B(i)G(i)R(i)", где i - номер бита [0..7].

Что то мне подсказывает, что это должно работать.

← →
MBo © (2006-04-28 06:02) [21]

>default © (27.04.06 18:01) [19]
>3 решена(линейное время)
Должно получиться порядка десятка строчек.

>Cash © (27.04.06 20:40) [20]
В решении неоправданно используется плавающая арифметика. Думаю, понятно, что задача может относиться к быстрой обработке изображений, и хотя бы Trunc(Power(2,i*3)) надо заменить на 1 shl ...
Однако есть методы и без циклов, с использованием хитрых битовых трюков.

← →
default © (2006-04-28 23:58) [22]

MBo © (28.04.06 06:02) [21]
3 я решил...
кстати, решение 2-ой как вам?известное вам решение такое?
временами над 7 думаю пока не клеится

← →
default © (2006-04-29 00:04) [23]

+[11]
то есть для N=43852 будем иметь разложение
F(43852)=F(39999)+F(3852)=F(39999)+F(2999)+F(852)=
F(39999)+F(2999)+F(799)+F(52)=F(39999)+F(2999)+F(799)+F(49)+F(2)
F(2)=0, значение остальных членов разложение определяется методом "поразрядного подсчёта единиц"

← →
MBo © (2006-04-29 07:27) [24]

>default
Да, для второй принцип подобный.
F(454)=f(0..99)+f(100..199)+f(200..454)
Для 0..99 (N девяток) - простая формула, (1,20,300...)
f(100..199) - 100+f(99)
f(200..454)=2*f(99)+f(0..54), что рекурсивно дальше раскладывается

>временами над 7 думаю пока не клеится

Для достижения O(N) нужна одна структура данных...

← →
default © (2006-05-01 12:05) [25]

7. на примере m=6
abcdefghijkl
формируем массив: max(abcdef)=m1,max(bcdef)=m2,max(cdef)=m3,max(def)=m4,max(ef)=m5
1)на первом шаге максимум определяется как: m1
2)на втором шаге максимум определяется как: max(m2,g)
3)на третьем шаге вычисляем и сохраняем значение: max(g,h)=M1
на третьем шаге максимум определяется как: max(m3, M1)
4)на четвёртом шаге вычисляем и сохраняем значение: max(M1, i)=M2
на четвёртом шаге максимум определяется как: max(m4, M2)
5)на пятом шаге вычисляем и сохраняем значение: max(M2,j)=M3
на пятом шаге максимум определяется как: max(m5, M3)
6)на шестом шаге вычисляем и сохраняем значение: max(M3,k)=M4
на шестом шаге максимум определяется как: max(M4,f)
то есть на данном шаге всё имеем чтобы начать процесс заново по такому же сценарию, алгоритм линеен, очевидно
MBo © (29.04.06 07:27) [24]
оно?

P.S. неужели и решение 5 тоже линейно?

← →
default © (2006-05-01 13:00) [26]

пардон, ошибка в [25]
поторопился:) на улице весна, солнышко:)

← →
MBo © (2006-05-01 13:11) [27]

>default © (01.05.06 12:05) [25]
Если я правильно понимаю, для произвольного m общая сложность будет N logM - так? Сделать подсказку?

> неужели и решение 5 тоже линейно?
нет, N logN.

← →
default © (2006-05-01 13:20) [28]

вот исправленный вариант
7. на примере m=6
abcdefghijkl
формируем массив по abcdef: max(abcdef)=m1,max(bcdef)=m2,max(cdef)=m3,max(def)=m4,max(ef)=m5
1)на первом шаге максимум определяется как: m1
2)на втором шаге максимум определяется как: max(m2,g)
3)на третьем шаге вычисляем значение: max(g,h)=M1
на третьем шаге максимум определяется как: max(m3, M1)
4)на четвёртом шаге вычисляем значение: max(M1, i)=M2
на четвёртом шаге максимум определяется как: max(m4, M2)
5)на пятом шаге вычисляем значение: max(M2,j)=M3
на пятом шаге максимум определяется как: max(m5, M3)
6)на шестом шаге вычисляем значение: max(M3,k)=M4
на шестом шаге максимум определяется как: max(M4,f)
после шестого шага в окне будет ghijkl и повторяем всё заново
"формируем массив по ghijkl..."
алгоритм, как нетрудно, видеть линеен
P.S. столько думал, а оказался по идее алгоритм довольно убогим...

← →
default © (2006-05-01 13:21) [29]

>оно? [28]
Смотрится логично, вроде бы на каждом шаге происходит формирование частных максимумов, но, честно говоря, трудно проанализировать полную корректность, путаюсь ;)

Известный мне алгоритм использует дек

+[28]
опишу почему алгоритм линеен, на всякий
алгоритм, как видно из его описания, можно сказать выполняется по заходам, в каждом заходе максимум в окне вычисляется m раз, причём на вычисление максимума в окне тратится как максимум две операции(2m за заход)
для выполнения "формируем массив по abcdef: max(abcdef)=m1,max(bcdef)=m2,max(cdef)=m3,max(def)=m4,max(ef)=m5" нужно не более 6 операций(по числу элементов к окне, m - для общего случая)
итого, на заход тратится, m+2m=3m операций и это для обработки m окон, то есть на окно идёт 3m/m=3 операции

> 5. Дан массив целых (в т.ч. и отрицательных) чисел.
> Найти, существует ли в нем непрерывный подмассив с суммой
> N.
> Пример [2 -1 3 5] N=4 -> да, 0..2 N=6 -> нет

> > неужели и решение 5 тоже линейно?
> нет, N logN.

MBo © (01.05.06 13:35) [30]
идея очень банальная, честно говоря испытал мало радости при нахождении алгоритма
abcdefghijkl, m=6
после первого сдвига справа вдвигается g
после второго сдвига справа вдвигается h (тут мы считаем max(g,h)=M1)
после третьего сдвига справа вдвигается i (тут мы считаем max(M1,i)=M2=max(g,h,i))
после четвёртого сдвига справа вдвигается j (тут мы считаем max(M2,j)=M3=max(g,h,i,j))
...до конца захода
массив же max(abcdef)=m1,max(bcdef)=m2,max(cdef)=m3,max(def)=m4,max(ef)=m5
даёт возможность на каждом шаге считать максимум в окне путём взятия максимума от нужного элемента массива и нужного Mi

2. Типа так получилось. Не совсем красиво, но работает
function Get1Count(S:integer):integer; var j,k,f,x,c:integer; begin result:=0; f:=1; j:=0; while s div f > 0 do begin c:=s mod f; k:=(s mod (f*10)) div f; x:=j*(f div 10); if k=1 then result:=result+x+c+1 else if k<>0 then result:=result+x*k+f; f:=f*10; inc(j); end; end;

>default © (01.05.06 14:01) [33]
Да, понятно.

Приведу метод с деком - это совмещенные стек-очередь, т.е. доступ к обоим концам есть.
Наверх дека кладется запись с номером и значением.

Тогда при каждом сдвиге окна, если номер внизу равен номеру числа, которое исчезло из окна, удалить этот элемент из дека
Создать очередную запись
Пока дек не пуст и значение наверху меньше очередного значения, удалять сверху
Поместить очередную запись наверх
Скользящий максимум - значение нижнего элемента

Итого: для последовательности длины n будет сделано n вставок в дек, n удалений из дека, и не более 2n сравнений.
(автор Sergey_)

>SergP © (01.05.06 14:12) [34]
>2. Типа так получилось. Не совсем красиво, но работает
Класс! Нерекурсивно и всего LgN шагов!

>TUser © (01.05.06 16:39) [38]
К сожалению, я имею только самое общее представление о суффиксных деревьях, и навскидку не знаю, так или не так...
А какой алгоритм за O(n^2) подразумевался?

Я тоже не знаю. Есть алгоритм Укконена, который позволяет строить суффиксное дерево за линейное время. А обход дерева, вроде бы, должен занимать как раз N log N, т.к. логарифм - это средняя высота листа, а всего листьев - O(N). Только вот не уверен.

Квадратичный алгоритм :))

for i:=0 to high do
sum := 0
for j:=i to high do
sum += A[j]
if sum = WhatWeNeed then
returm i, j

>TUser © (02.05.06 11:56) [40]
Можно и несколько другим квадратичным алгоритмом воспользоваться:
Построить массив частичных сумм за линейное время
s[0]=A[0]
s[i] = s[i-1]+A[i]
Затем квадратичная часть - сравнение разностей s[i]-s[j] c искомой суммой.

Отсюда осталась пара шагов модификации до NlogN...

Пятничные задачки для программистов. Найти похожие ветки