IMHO.WS - Задачки для программистов

IMHO.WS (http://www.imho.ws/index.php)

- Программирование (http://www.imho.ws/forumdisplay.php?f=40)

- - Задачки для программистов (http://www.imho.ws/showthread.php?t=57497)

Ну вообще-то это задачки для програмиста а не для математика.

Цитата:

ARTi:
можно и рекурсию устроить, да такую, чтоб с переполнением стека

Ну так у меня максимальная глубина рекурсии это M, так что переполнение стэка там не скоро будет.

Цитата:

ARTi:
Я облажался, т.к. формулы этой не помню

А я когда меня просят решить такую вещь даже не думаю есть формула или нету, а сразу пишу код.

joker99

Цитата:

А я когда меня просят решить такую вещь даже не думаю есть формула или нету, а сразу пишу код

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

Кто знает как написать класс на с++ так, что бы от него нельзя было унаследовать?
Т.е. при попытке унаследовать класс - код не компилировался.

Так:

Код:

class UnInheritableClass

{

friend UnInheritableClass CreateUnInheritableClass();



private:

        UnInheritableClass()

        {

        

        }

};



UnInheritableClass CreateUnInheritableClass()

{

        return UnInheritableClass ();

}

От класса UnInheritableClass нельза наследовать, а создаётся он через функцию CreateUnInheritableClass()

joker99

Во-первых, CreateUnInheritableClass() должен быть статическим - иначе его нельзя будет вызвать.

Во-вторых, хотелось бы без приват конструктора.

Во первых CreateUnInheritableClass() не member function.

Во вторых...., сейчас подумаю :confused:

Вот вам еще задача:
Дана матрица где большинство значений нули. Например:

Код:

Представьте её в более компактном виде.
Удачи.

Если нулей бо;ьше половины, то надо сохранить только не нули, с ихними индексами, т.е для твоей матрицы:

(2,0),(1,4),(3,7),(1,11),(5,15)

имеем 10 числ для 16 местной матрицы.

joker99

совершенно верно, маэстро :)

А как вам такая задачка:

Задана строка, содержащая выражение вида a?b?c?f?e=zz, где ? принадлежит множеству (+,*,-,/). a,b,c,....,z - натуральные числа, zz - контрольный результат. Необходимо написать программу которая выдает все возможные выражения при вычислении которых получим число zz . Пример: 2?2=4 Вывод : 2+2=4 2*2=4

Не напрягаю, но она очень интересна по своему.

Цитата:

Напоминает рекурсивный обход лабиринта. Старо.

По поводу матрицы... то решение хранить элементы с координатами, имея в целом здравое ядро, явное школярство... Хранить чтобы хранить, это извините за выражение форма "программного тихо сам с собою ;)"

Есть два типа задач --- прямой рандомальный доступ (если реализован за О(1) то ничего более не надо) и выборка (строки/столбца, например для умножения на вектор, реже чего-либо другого)

Так вот если хранить с координатами то рандомальный доступ О(к-во элементов в матрице), выборка тоже О(к-во элементов в матрице) (тут можно малость оптимизировать это О(к-во элементов в матрице) но несильно)... т.е. если матрица велика, то даже для очень редкой, это немало и соотв. плохо...

Заметно лучше двумерный связный список: выборка строки/столбца/отдельного элемента О(к-во элементов в строке/столбце)... затраты на память: линейно по стороне плюс к-во элементов... Если величина к-во элементов в строке/столбце все еще велика заменить список скип-листом тогда доступ к элементу станет логорифмическим...

a_ber

Да, но задача была в экономии места, а не в уменьшении времени выборки.

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

Что-то темка заглохла... А мне периодически подгоняют интересные задачи. Вот вчера подкинули еще одну - пока не решил, не успокоился - не мог оторваться.

Итак. Мы имеем числовую прямую положительных чисел (т.е. >0). Среди этих чисел можно выделить такие, которые состоят из неповторяющихся цифр (например: 64183 не содержит одинаковых цифр) и составить из них новую последовательность, элементы которой упорядочены и имеют номера: число 1 - №1, 2 - №2, ..., 123 - №100, ... Задача проста как угол стола: имея номер числа из этьой последовательности, определить само число.

Есессно, можно банально решить перебором, но всего таких чисел может быть 8877690 штук - перебирающая софтинка основательно задумается... Посему, в том условии, что давали мне, стояло ограничение на время работы программы - 5 секунд. Но, могу вам сказать, на деле требуется на порядок меньше времени.

Это не конкурс - просто разминка для мозгов. Итак, господа программеры, понеслась! Жду ваших решений ;)

сейчас нет времени проверять, но закономерность тут в принципе простая.

После цифры 10 в каждой десятке одно число выбрасываем. Значит: если нужна позиция 43,
1) из трёх десятков выкидываем по числу
2) имеем 46 (43+3) и до цифры 40 включительно всё проверено.
3) проверяем от 41 до 46 перебором, выкидываем 44
4) ответ: 47 (46+1)

С сотнями, тысячами и т.д. аналогично.
:claps:

Эээ... Не совсем въехал. Можешь продемонстрировать алгоритм на примере: число №1357 = 2305.
И кстати, сделать прогу можно вообще без перебора чисел и без определения, удовлетворяет ли оно условию (неповторяются цифры) - у тебя это присутствует в пункте 3.

пример делать некогда. весь смысл в том, что двигаем цифру дальше.
Простейший пример: позиция 12. находим количество пропущеных (один пропущеный - номер 11) и прибавляем к позиции это количество. 12+1 = 13.

Можно и без переборов, но там уже выйгрыш пинимальный.

EvroStandart
Гыхм... Меня тоже посещали подобные идеи, но в конце концов я от них отказался - решил делать так, чтобы перебор вообще не требовался, даже для десятка значений. А насчет выигрыша - сложно сказать, нужно сравнивать программы, а я пока никак не могу въехать в твой способ (хотя, думаю, кто-то потом скажет, что въехать в мой намного сложнее ;))

Подожду еще - может кто что другое предложит...

n= №1357
-- опред кол-ва цифр
цикл
n1 = 10 0-9
n2 = 9*9 +n1 10-99
n3 = 9*9*8 +n2 100-999
n4 = 9*9*8*7 +n3 1000-9999
n5 = 9*9*8*7*6 +n3 10000-99999
определили ближ меньшее nX - мы знаем сколько цифр
m1=n-nX - сколько неповтор. чисел X цифр

определим 1 цифру (например из 5 цифр)
для 1 9*8*7*6
для 2 9*8*7*6+для 1
для 3 9*8*7*6+для 2

т.е. m1 берем по модулю 9!/5! - определили 1 цифру

для нее получили m2=m1- (9!/5!*(цифра -1)
для второй цифры (и далее немного меняя формулу)
для 1 9*8*7
для 2 9*8*7+для 1
для 3 9*8*7+для 2
для нее получили m3=m2- (9!/6!*(цифра2 -1)

Вот такой алгоритм приблизительно

EvroStandart
Попробовал твой алгоритм на числе 99. Должно получиться 120 (копи+паст + изменение пары чисел - я их подчеркнул):

После цифры 10 в каждой десятке одно число выбрасываем. Значит: если нужна позиция 99,
1) из восьми десятков выкидываем по числу
2) имеем 107 (99+8) и до цифры 91 включительно всё проверено.
3) проверяем от 92 до 107 перебором, выкидываем 99, 100, 101
4) ответ: 110 (107+3)

Не получается... :rolleyes: Или я что-то неправильно понял?

lalexa100
Эээ... Опять-таки, можно пример? Скажем с числом 123 (№100). Или хотя бы формулы по-подробнее расписать и без ошибок (две скобки открываем - одну закрываем)

И кстати, насчет "n1 = 10 0-9": последовательность состоит из положительных чисел, т.е. 0 в нее не входит.

Насчет ошибок - я подал только идею, ее еще до ума довести нужно.
число 123 № 100
итак
n1=10 - не катит
n2=10+81=91 - не катит
n3=91+91*8 > 100 катит значит 3 цифры
ищем первую 100-91=9
100-199 9*8=72 > 9 катит - значит цифра 1
ищем вторую
100-109 = 8 (первая 1 вторая 0 третья 2-9) не катит
110-119 выпадает из рассмотрения (первая = второй)
120-129 = 8+8 катит вторая 2
ну а последняя цифра 9 - 8 = 1
из списка 0.2.3.4.5.6.7.8.9 первая

Гыхм... Я уже ухожу сегодня, появлюсь теперь не знаю когда. Так что выкладываю свое решение. В процессе решения мне на ум приходили оба предложенных решения (и еще парочка), но первое я сразу отмел из-за наличия перебора, второе - не сумел довести до ума, не хватило терпения (или соображалки).

Может мои рассуждения вам покажутся чересчур сложными, но решал задачу я именно так (на подобные выкладки меня натолкнули воспоминания о прочитанном от корки до корки "Искусстве программирования" Кнута).

Итак. Для начала строим дерево следующего вида: корень (уровень №0) - некий пустой элемент, из него выходят девять ветвей к узлам 1, 2, ..., 8, 9 - уровень №1; из каждого эелемента 1-го уровня также выходят ветви т.о., чтобы путь к ним по узлам (цифрам в узлах) не содержал повторяющихся цифирей, например, из узла (1) 1-го уровня выходят ветви к узлам 0, 2, 3, ..., 8, 9. И т.д. - всего 10 уровней, что очевидно - не может существовать десятичное число с неповторяющимися цифрами длиной более 10. Т.о., при проходе сверху-вниз по этому дереву всегда получается "разноциферное" число.

Само это дерево в программе не потребуется, и строить его не нужно будет. Важны некоторые характеристики уровней. А именно:

T - количество ветвей, спускающихся в текущий уровень из любого элемента предыдущего уровня. Т.е., фактически, какое количество цифр можно добавить к уже существующему "разноциферному" числу, не нарушая его. Это число легко определяется следующим образом:
T[1] = 9;
T[i] = 11 - i, 1<i<=10.
F - общее число узлов в уровне, т.е., в приложении к данной задаче, - количество 1-, 2-, 3-значных "разноциферных" чисел и т.д. Это число тоже легко вычисляется:
F[1] = T[1];
F[i] = T[i] x F[i - 1], 1<i<=10.
S - общее число узлов в дереве по текущий уровень включительно или, другими словами, количество "разноциферных" чисел длины не более 2, 3, и т.д.:
S[1] = F[1];
S[i] = F[i] + S[i - 1], 1<i<=10.

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

Далее, зная N (номер искомого числа), легко вычисляется K - количество разрядов в нем: сперва записываем в K единицу, а потом увеличиваем, пока S[K] < N.

После этого я запоминал номера узлов каждого уровня (начиная с K-го и вверх), через которые нужно пройти, чтобы получить искомое. В результате получил массив A из K элементов.

Теперь, зная номера узлов в каждом уровне, легко определить путь прохода дерева с одновременным формированием числа. Для этого я просматривал массив A в прямом порядке (от 1 до K) и находил номера цифр ((A[i] - 1) mod T[i]) из строки W (в начале, перед первым шагом = '123456789'), добавляя их к результирующей строке Z и удаляя из W.

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

Код:

uses

  crt;



var

  i, k, n:    longint;

  a, t, f, s: array [1..10] of longint;

  w, z:       string;



begin

  clrscr;

  write('n = '); readln(n);

  if (n > 9) then begin

    fillchar(t, sizeof(t), 0); t[1] := 9;

    fillchar(f, sizeof(f), 0); f[1] := t[1];

    fillchar(s, sizeof(s), 0); s[1] := f[1];

    for i := 2 to 10 do begin

      t[i] := 11 - i;

      f[i] := t[i] * f[pred(i)];

      s[i] := f[i] + s[pred(i)];

    end;

    if n > s[10] then z := 'no solutions' else begin

      k := 1;

      while s[k] < n do inc(k);

      fillchar(a, sizeof(a), 0);

      for i := k downto 1 do begin

        if i = k then a[i] := n - s[i - 1]

                 else a[i] := succ(pred(a[i + 1]) div t[i + 1]);

      end;

      w := '123456789';

      z := '';

      for i := 1 to k do begin

        z := z + w[succ(pred(a[i]) mod t[i])];

        delete(w, succ(pred(a[i]) mod t[i]), 1);

        if i = 1 then w := '0' + w;

      end;

    end;

  end else if n > 0 then str(n, z) else z := 'no solutions';

  writeln('r = ', z);

  readkey;

end.

К вопросу о uninheritable class

Я бы лично тоже решил задачку с private конструктором, но как видно это не то что задумывалось. Конечно можно воспользоваться языковыми примочками типа final (PHP), sealed (C#), NonInheritable (VB), но я так думаю что уважаемый Фей-Мод Dimm :cool: хочет другое решение. К сожалению решения я ещё не нашел, но пока баловался, пришел к интересной штуке с вложенными классами. Вот пример:

Код:

class A1

{

public: 

        A1(){};

private:

        class A2

        {

        public:

                A2(){};

        };

};

От класса А2 не только нельзя унаследовать (что собственно отвечает условиям задачи) но и создать вне класса А1 тоже нельзя. А может это и был ответ? /ooc crosses fingers :biggrin:

Дорогие форумчане, помогите решить такую простую задачу.
А то просто ум за разум заходит , арешения нет ...
Нам дано несколько букв (любое количество , по порядку, и каждая только по одному разу) нужно выдать все возможные варианты перебора по позициям.
Например:
A,B,C.

получаем
A,C,B
C,A,B
C,B,A
B,A,C
B,C,A

и так с любым количеством.

stastan
Это называется перестановками. Смотри алгоритм и пример решения тут
http://opensource.com.ua/contents/978546900444p.html

stastan

Код:

uses

  crt;



var

  s: string;



procedure write_all (s, p: string); far;

var

  i: integer;

begin

  if length (p) = length (s)

    then writeln (p)

    else for i := 1 to length (s) do

      if pos (s[i], p) = 0 then write_all (s, p + s[i]);

end;



begin

  clrscr;

  write ('input string: '); readln (s);

  write_all (s, '');

  write ('press any key to exit...');

  readkey;

end.

З.Ы. ЕЖ - может займемся синхронным плаванием? ;) У нас хорошо получается. :)

to StPatrick
Не знаю, но на моей Visual Studio .NET скомпилировался следующий код:

Код:

class A1

{

public: 

A1(){};

private:

       class A2

      {

                        public:

                        A2(){};

                };



           class A2_new:public A2{

           public:

                   A2_new(){}

           } param;

};

to Crazy_kettle
Ту нет ничего удивительного. Внутри класса А1, А2 можно использовать как угодно. Попробуй так:

Код:

class A1{...};

int main()

{

    A1 *tmpA1 = new A1();

    A2 *tmpA2 = new A2(); // вот так не выйдет !

}

Цитата:

GOre01:
Ту нет ничего удивительного. Внутри класса А1, А2 можно использовать как угодно. Попробуй так

А задача, какая была? ;)

P.S. Если я ничего не путаю, то достукиваться до класса A2, нужно через A1::A2.

Google Code Jam Europe 2006

Началась регистрация участников конкурса Google Code Jam Europe 2006. Зарегиться можно всем желающим с Monday, May 1 по Tuesday, May 23. Само собой, будут призы. Код можно писать на Java, C++ или C#.
Подробности здесь

PS: Если не туда закинул, поправьте. Просто, вроде как, это задачи для программеров. Можно здесь же и обсудить различные методы решения.

PPS: Конкурс еще не начался, но различные задачи разного уровня сложности можно решать уже сейчас. Если не ошибаюсь, то за это начисляются балы.

Вообщем, читаем правила, регистрируемся и пробуем выйти в призеры. Всем удачной игры :yees:

Совсем вылетело из головы. Участие могут принимать All individuals who are legal residents of Europe, Africa and the Middle East may register and compete in the Google Code Jam Europe 2006 provided they physically reside in an eligible country from May 1 through June 29, 2006. В том числе и жители Росии.