|
|
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Добрый день! Предлагаю сообществу подумать над задачкой. Типичный прогерИсходные данные: массив с числами типа Integer. Вам нужно написать функцию, которая на входе получит исходный массив, а на выходе вернет массив, в котором каждое значение получено путем произведения всех значений исходного массива с отличным от текущего индексом. Для ясности приведем пример. Допустим, исходный массив имеет вид: [1, 7, 3, 4]; Тогда функция должна вернуть: [84, 12, 28, 21]; Расчет значений выглядит так: [7*3*4, 1*3*4, 1*7*4, 1*7*3]; Дополнительные условия: 1. Нельзя использовать деление. 2. Функция должна быть с наименьшими затратами памяти и времени выполнения. Скажу честно что задачка не моя. Стырено из соц-сетей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 01:01 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
мы ее уже решили. 18335732 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 02:13 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
а Марк сопротивлялся когда я просил у него идеи в том обсуждении :p ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 03:39 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Не помню суть спора. Но кажется моё пожелание заключалось в том что формулировки надо писать на русском языке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 13:03 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Не смотрел решения, рискну предположить, что нужно сформировать два вспомогательных массива, в одном будет произведение всех элементов 0.. i -1, в другом - i+1..N-1. Результат получается путем скалярного их перемножения. Вспомогательные массивы заполняются, естественно, перемножением предыдущего элемента на текущий (второй - в обратном порядке). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 13:45 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
У меня была мысль умножать на 1/a[i] в хитром базисе. Как-бы в целых числах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 14:17 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
maytonумножать на 1/a[i] как получить 1/a[i] без деления? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 14:18 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Это загадка великая есть. Не знаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 15:46 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Марк, да нет. Вы говорили о том что толку в решении задач Скиены с точки зрения развития в IT сфере нет ) Никаких споров у нас с вами не было) Наконец вы оторвались от ваших китайцев(вы по-моему ими занимались) и вернулись к Скиене :D Соколинский Борис скалярного их перемножения что вы имеете ввиду ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 16:20 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercuryМарк, да нет. Вы говорили о том что толку в решении задач Скиены с точки зрения развития в IT сфере нет ) Никаких споров у нас с вами не было) Наконец вы оторвались от ваших китайцев(вы по-моему ими занимались) и вернулись к Скиене :D Соколинский Борис скалярного их перемножения что вы имеете ввиду ? проще написать Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 16:39 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercury, ох уж этот Майтон. Постит задачки из социальных сетей. Толи дело - академичные издания.... Мдя... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2015, 16:51 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис проще написать скалярного произведения в вашем коде нет ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 01:47 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercuryскалярного произведения в вашем коде нет ) Ну да, неправильный термин. Еще можно одним вспомогательным массивом обойтись. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 08:31 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис, можно, всё верно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 09:56 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Типичный прогер1. Нельзя использовать деление. 2. Функция должна быть с наименьшими затратами памяти и времени выполнения. протеворичивые условия. предлагаю использовать возведение в степень -1 и умножение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 12:00 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Там по условию задан массив целых. Как возводить целое в степень -1 с сохранением условий задачи ХЗ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 12:44 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
maytonТам по условию задан массив целых. Как возводить целое в степень -1 с сохранением условий задачи ХЗ. в условии есть получить массив и вернуть массив. а что там в черном ящике - ограничено только пунктами 1 и 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 15:50 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
авторпредлагаю использовать возведение в степень -1 и умножение. Предлагаю вместо 'привет' говорить 'здравствуйте' ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2015, 17:03 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
mayton, похоже, что можно решить эту задачу без дополнительной памяти ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2015, 14:07 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Чтобы не отвлекаться на эмуляцию арифметического сдвига вправо (SAR) здесь для хранения целых чисел используется тип cardinal: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2015, 14:57 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
mayton, А практический смысл!? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.12.2015, 12:28 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Улучшенная версия: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.12.2015, 23:23 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Areostarmayton, А практический смысл!? Это очень хороший вопрос. По сабжу к каждому студенту который просит решить лабу я могу обращаться с таким-же встречным. Но я надеюсь что в нашем скромном форуме найдется место головоломкам без SR. Не так ли? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.12.2015, 12:19 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
mayton, Есть интересный вариант задачи с похожим решением: Длинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M. Множители никак не упорядочены и не обязательно просты. Известно, что B=A*х, где x - короткое. Найти x. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 20:35 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, если B=A*х то x=B/A Или я чет не так понял задание. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 20:45 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
mayton, Все так. Только этот результат требуется получить без деления и без использования длинных чисел. Сорри, что сразу не написал это в условии, т.к. почему-то посчитал это условие разумеющимся в свете предыдущей задачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 20:57 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Я понял. Надо подумать. Скорее всего решение этой задачи будет базироваться на циклических вычитаниях и (возможно умножениях). Как алгоритм Евклида. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 21:02 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Забавно. А вот ещё тривиальщины на закуску, на случай, если и в этой задаче делить нельзя. Если авторМножители никак не упорядочены и не обязательно просты., то надо: разложить множители до простых, получить классические представления в виде перемножения простых множителей: A* и B* упорядочить оба представления, что поможет быстро... ...вычесть A*\B* и так получить X для фанатов: вычесть B*\A*, получить пустое множество, и так убедиться, что - автор не соврал! - X и впрямь целочисленное. для фанатов-префанатов: выполнять два последних пункта одновременно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 21:03 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
MrCat, Забавно, но, оказывается, можно проще ) См. решение предыдущей задачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 21:08 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Лучше отдельным топиком. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2015, 21:14 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, а что такое короткие множители ? Вы имеете ввиду факторизацию, или что-то другое ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2015, 01:57 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercury, Обычно программная реализация длинного целого типа для работы с очень большими числами основана на некотором ("коротком") целочисленном типе, который поддерживает компилятор. Программисты, с ними работающие, для собственного удобства используют очевидный жаргон. Например, "умножение длинного на короткое". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2015, 08:13 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovmaytonЛучше отдельным топиком. Здесь: http://guildalfa.ru/alsha/node/31 Не. Ну это неинтересно. Блог господина Шарахова нам недоступен для каментов. Лучше всё таки поднять на скруле. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2015, 13:42 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercuryAleksandr Sharahov, а что такое короткие множители ? Вы имеете ввиду факторизацию, или что-то другое ? Мне почему-то вспомнилось Умножене Карацубы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2015, 13:45 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
mayton, Топик разместил у себя в блоге, чтобы, во-первых, он не затерялся и остались следы, и, во-вторых, там ожидается весьма интересное продолжение, которое давно планировал, но все никак не могу собраться из-за нехватки времени. А комментарии можно хоть здесь, хоть там писать - не проблема. Умножение Карацубы немного из другой оперы. Если грубо, то оно используется для оптимизации умножения столбиком длинных чисел, а для умножения длинного на короткое оно не требуется. Но тема даже не в этом, а в том, что на самом деле и длинное не всегда нужно, иногда оказывается достаточно его последней цифры. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2015, 14:09 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovmayton, Есть интересный вариант задачи с похожим решением: Длинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M. Множители никак не упорядочены и не обязательно просты. Известно, что B=A*х, где x - короткое. Найти x. XOR всех множителей a[i] и b[j] даст требуемый результат ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 03:35 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercuryAleksandr Sharahovmayton, Есть интересный вариант задачи с похожим решением: Длинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M. Множители никак не упорядочены и не обязательно просты. Известно, что B=A*х, где x - короткое. Найти x. XOR всех множителей a[i] и b[j] даст требуемый результат Пусть a=2, b=2*2*2. Тогда x=2*2, но XOR=0. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 07:58 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, ваш контрпример противоречит условию Aleksandr Sharahov Известно, что B=A*х, где x - короткое. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 08:02 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercuryAleksandr Sharahov, ваш контрпример противоречит условию Aleksandr Sharahov Известно, что B=A*х, где x - короткое. В чем противоречие? A состоит из одного целого множителя, равного 2, который укладывается в отведенное количество бит (скажем 32). B состоит из трех целых множителей, каждый из которых также равен 2. B=A*4. Т.е. x=4 и x - короткое (укладывается в отведенное количество бит). На мой взгляд, соответствие условию полное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 08:13 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov На мой взгляд, соответствие условию полное. В постановке задаче вы фигурировали термином "короткое число". Определили оба числа как произведение коротких чисел и далее вы сказали о том, что числа отличаются на одно короткое число. Aleksandr SharahovДлинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M. Множители никак не упорядочены и не обязательно просты. Известно, что B=A*х, где x - короткое. Из чего был сделан вывод о том, что данное короткое число должно принадлежать одному из множеств коротких чисел соответствующих числам A и B, что не совпадает с вашими требованиями к данной задаче. В таком случае, мне кажется, лучше будет озвучить постановку задачи следующим образом: Пусть , где . Известно, что . Найти x не используя операцию деления ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 08:47 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Кстати, как я понимаю число 0 подходит под данное выше определение короткого числа 1. Пусть 0 будет присутствовать в одном из чисел. Что на выходе даст ваш алгоритм ? 2. Пусть 0 присутствует в обоих числах, при этом никаких различий в числах более нет. Что на выходе даст ваш алгоритм ? 3. Пусть 0 присутствует в обоих числах, существуют различия в числах. Что на выходе даст ваш алгоритм ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 09:00 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercury, Вывод о том, что короткое число x должно принадлежать одному из множеств коротких чисел, соответствующих числам A и B, неверен. Он никак не следует из того, что x - короткое. Похоже, ваша формулировка задачи полностью эквивалентна моей, но, несомненно, выглядит гораздо красивее ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 09:56 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
SashaMercuryКстати, как я понимаю число 0 подходит под данное выше определение короткого числа 1. Пусть 0 будет присутствовать в одном из чисел. Что на выходе даст ваш алгоритм ? 2. Пусть 0 присутствует в обоих числах, при этом никаких различий в числах более нет. Что на выходе даст ваш алгоритм ? 3. Пусть 0 присутствует в обоих числах, существуют различия в числах. Что на выходе даст ваш алгоритм ? Если не ошибаюсь, алгоритм отслеживает все эти особые случаи и в качестве результата выдает 0 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 09:59 |
|
||
|
Вторничная новогодняя задачка
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, конечно мой вывод был неверен ) Но это недопонимание с моей стороны возникало по причине присутствия данного термина. Пусть например оба числа равны 0, в таком случае x может быть любым числом. Неформальное определение "короткое число" позволяет нам провернуть подобное. Может быть 0 всё-таки не должен присутствовать в постановке задачи ?Или это не так ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2016, 10:16 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1340821]: |
0ms |
get settings: |
6ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
156ms |
get topic data: |
7ms |
get forum data: |
2ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
| others: | 203ms |
| total: | 448ms |

| 0 / 0 |
