|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
в теме "Почему ООП так популярно?" я затронул интересную олимпиадную задачку. вскоре на нее были даны различные варианты ответов... так вот выкладываю ниже свои и не только решения, хочу предложить всем заинтересовавшимся людям попробовать ее решить в том языке и тем способом, который они посчитают нужным, давайте померимся возможностью языков и методов, быть может неожиданно окроются плюсы или достоинства последних... Задача------ Дан массив из K+L элементов. Нужно поменять местами две его части: 0..K-1 и K..K+L-1, не используя дополнительной памяти объёмом Z(K+L)за время O(K+L). ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 17:02 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
первый мой вариант ранний Код: plaintext 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. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 17:04 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
более поздний переосмысленный Код: plaintext 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 17:09 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Даю ответ, придумайте загадку? :) Я как чуть-чуть математик интересуюсь задачей сущестования. Существования формулировки задачи на естественном языке. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 17:18 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
авторне могли бы вы господа решить данную задачу на любом из трех общепринятых языках(С, Бэйсик или Паскаль)... Код: plaintext 1. 2. 3.
Перевожу теперь на нормальный. Код: plaintext 1. 2. 3. 4. 5.
Так ? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 17:38 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
А-а. Какой параметр измеряем? "Кол-во перемещений элементов"? Сколько дается "свободных ячеек" для промежуточного хранения? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 17:42 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
И? Тривиально доказуемо, что меньше, чем за K+L перемещений элементов это сделать нельзя. (T>=K+L) Также тривиально, что при последовательном обходе всех циклов любой перестановки каждый элемент перемещается не более одного одного раза. (T<=K+L) Несколько менее тривиально -- cut here -- p будем считать циклическим сдвигом вправо на 1 позицию p k == p * p ... *p -- последовательным применением p k раз p K+L == 1 в этой группе p -- примитивный элемент, его степени образуют все элементы циклической группы. p L (то самое, необходимое нам преобразование массива) образует подгруппу с кол-вом элементов (K+L)/НОД((K+L), L) = (K+L)/НОД(K, L) => каждый цикл в результирующей перестановке имеет длину указанную в продолжении ниже -- cut here -- доказуемо то, что количество циклов N = НОД (K, L) и длина их Q = (K+L)/НОД(K, L) а также, что первые N (если, конечно, N > 1 :) ) элементов массива (это можно и самостоятельно :) ) принадлежат разным циклам перестановки. Выходит, что K+L, c одной временной ячейкой, и оптимальнее не существует. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 20:00 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
QИ? Тривиально доказуемо, что меньше, чем за K+L перемещений элементов это сделать нельзя. (T>=K+L) Также тривиально, что при последовательном обходе всех циклов любой перестановки каждый элемент перемещается не более одного одного раза. (T<=K+L) Несколько менее тривиально -- cut here -- p будем считать циклическим сдвигом вправо на 1 позицию p k == p * p ... *p -- последовательным применением p k раз p K+L == 1 в этой группе p -- примитивный элемент, его степени образуют все элементы циклической группы. p L (то самое, необходимое нам преобразование массива) образует подгруппу с кол-вом элементов (K+L)/НОД((K+L), L) = (K+L)/НОД(K, L) => каждый цикл в результирующей перестановке имеет длину указанную в продолжении ниже -- cut here -- доказуемо то, что количество циклов N = НОД (K, L) и длина их Q = (K+L)/НОД(K, L) а также, что первые N (если, конечно, N > 1 :) ) элементов массива (это можно и самостоятельно :) ) принадлежат разным циклам перестановки. Выходит, что K+L, c одной временной ячейкой, и оптимальнее не существует. :) спасибо MasterZiv за то что привел условие задачи... про K+L вы наверно что-то напутали, либо я вас не допонял, последний вариант имеет минимальное число перестановок (K + L)/2 максимальное как раз K+L, простейший тестовый вариант в доказательство моих слов в поседнем примере К = 5 L = 5 и посчитайте число перестановок... и я не ящу более оптимального решения этой задачи, я лишь хотел увидеть и оценить е реализации на различных языках... ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 20:21 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
QА-а. Какой параметр измеряем? "Кол-во перемещений элементов"? Сколько дается "свободных ячеек" для промежуточного хранения? количество ячеек для промежуточного хранения минимально разумное - при обмене двух элементов не следут изголяться вычитаниями сложениями или перексориваниями, важнейший параметр конечно же количество перемещений... хотя мне более интересна реализация на других языках ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 20:26 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Для простоты я считал единицей работы ОДНО перемещение ОДНОГО элемента в ОДНОМ направлении. :) Навроде того, как работает дефрагментация практически всего. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 20:55 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Кстати, в реальной задаче, которая, разумеется, "без перексориваний" (дефрагментация диска произвольной заполненности, например), все равно потребуется два буфера в памяти: один под временное хранение данных кластера, другой, собственно для переписывания одного кластера в другой. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 21:08 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Да пошла эта оптимизация... Код: plaintext 1. 2.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 22:30 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
??? Код: plaintext 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 22:45 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Q??? Код: plaintext 1.
Чего изволите? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 22:51 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Аа, дошло ... ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 22:51 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Q, Ну аффтару же непременно перестановки были нужны ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 22:52 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Q??? Код: plaintext 1.
А так - то и мы могем Код: plaintext 1. 2. 3. 4.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:00 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
$_ = "1,22,333,4444,55555,666666,7777777,88888888"; print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n"; ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:27 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Q$_ = "1,22,333,4444,55555,666666,7777777,88888888"; print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n"; Круто. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:34 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
QДля простоты я считал единицей работы ОДНО перемещение ОДНОГО элемента в ОДНОМ направлении. :) Навроде того, как работает дефрагментация практически всего. хм... я так и подумал, но тогда у меня получается какая - то нестыковочка, т.е. минимальное число перестановок всеравно (K+L)*3/2, так как одна перестановка равна 3 "физическим":) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:43 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Q$_ = "1,22,333,4444,55555,666666,7777777,88888888"; print $_."\n";s/^((\d+,){6})(.+)/\3,\1/;chop;print $_."\n"; а это на каком диалекте?) виуально похоже на струтуру типа список... ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:44 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
SQL_LamerQ??? Код: plaintext 1.
А так - то и мы могем Код: plaintext 1. 2. 3. 4.
а у вас что за язык? ну да) 29 строк паскаля против 3, круто конечно) этакими темпами програмисты скоро вообще программы писать не будут) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:47 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
Это PERL на plain C тоже недолго: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2009, 23:55 |
|
решение тривиальной алгоритмической задачи разными подходами и средствами
|
|||
---|---|---|---|
#18+
QЭто PERL на plain C тоже недолго: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
да С это С... но вот конструкции Код: plaintext
разбираться в чужом коде на С неимоверно тяжко... быть может просто нет привычки... из всех вариантов пока, конечно, короткий и самый понятный для меня, не знающего этих языков ,это у SQL_Lamer. А вообще интересно наблюдать как можно решить задачу на другом неизвестном тебе языке... ... |
|||
:
Нравится:
Не нравится:
|
|||
30.03.2009, 00:11 |
|
|
start [/forum/topic.php?fid=16&fpage=11&tid=1340008]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
61ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
68ms |
get tp. blocked users: |
1ms |
others: | 238ms |
total: | 418ms |
0 / 0 |