Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2006.05.28;
Скачать: CL | DM;

Вниз

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

 
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]

MBo ©   (01.05.06 13:11) [27]
оно? [28]


 
MBo ©   (2006-05-01 13:35) [30]

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

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


 
default ©   (2006-05-01 13:49) [31]

+[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 операции


 
TUser ©   (2006-05-01 13:54) [32]


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


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


 
default ©   (2006-05-01 14:01) [33]

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


 
SergP ©   (2006-05-01 14:12) [34]

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;


 
MBo ©   (2006-05-01 14:12) [35]

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

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

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

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


 
default ©   (2006-05-01 14:21) [36]

SergP ©   (01.05.06 14:12) [34]
5 попробуй интересно что там


 
MBo ©   (2006-05-01 14:30) [37]

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


 
TUser ©   (2006-05-01 16:39) [38]

> TUser ©   (01.05.06 13:54) [32]

Забыл написать :) Строим суффиксное дерево и обходим его. Так?


 
MBo ©   (2006-05-02 06:26) [39]

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


 
TUser ©   (2006-05-02 11:56) [40]

Я тоже не знаю. Есть алгоритм Укконена, который позволяет строить суффиксное дерево за линейное время. А обход дерева, вроде бы, должен занимать как раз 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



Страницы: 1 2 вся ветка

Текущий архив: 2006.05.28;
Скачать: CL | DM;

Наверх




Память: 0.59 MB
Время: 0.055 c
15-1146583222
Новичоккк
2006-05-02 19:20
2006.05.28
Математическая задачка


2-1147280995
BAngel
2006-05-10 21:09
2006.05.28
как создать свой цвет


2-1147154902
Sergey Masloff
2006-05-09 10:08
2006.05.28
Проблема с кодировками. Написал плагин к Outlook но сабж...


2-1147286075
SerGH
2006-05-10 22:34
2006.05.28
При закрытии возникает ошибка


11-1126546794
Stargazer
2005-09-12 21:39
2006.05.28
TOnMessage в новом KOL