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

[joker99]

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

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

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

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

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

joker99

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

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

[Dimm]

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

[joker99]

Так:

class UnInheritableClass
{
friend UnInheritableClass CreateUnInheritableClass();

private:
	UnInheritableClass()
	{
	
	}
};

UnInheritableClass CreateUnInheritableClass()
{
	return UnInheritableClass ();
}

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

[Dimm]

joker99

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

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

[joker99]

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

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

[Dimm]

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

2 0 0 1
0 0 3 0
0 0 1 0
0 0 5 0

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

[joker99]

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

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

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

[Dimm]

joker99

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

[Rundll]

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

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

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

[nibl]

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

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

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

[a_ber]

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

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

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

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

[Dimm]

a_ber

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

[a_ber]

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

[Ghost]

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

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

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

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

[EvroStandart]

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

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

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

[Ghost]

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

[EvroStandart]

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

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

[Ghost]

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

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

[lalexa100]

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)

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