|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish~2e9 решений полузадачиНе понял при чем здесь два миллиарда. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:28 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, я же и говорю о ширине коридора. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:36 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawish~2e9 решений полузадачиНе понял при чем здесь два миллиарда. это бред (). очередное доказательство, что нефиг трендеть на основе домыслов, а надо запросы писать. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 21:32 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
обычным SQL за 0.2 сек на Оракл 9.2? это реально :-) таблицы Код: plsql 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.
запрос Код: plsql 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. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. 281. 282. 283. 284. 285. 286. 287. 288. 289. 290. 291. 292. 293. 294. 295. 296. 297. 298. 299. 300. 301. 302. 303. 304. 305. 306. 307. 308. 309. 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. 320. 321. 322. 323. 324. 325. 326. 327. 328. 329. 330. 331. 332. 333. 334. 335. 336. 337. 338. 339. 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351. 352. 353. 354. 355. 356. 357. 358. 359. 360. 361. 362. 363. 364. 365. 366. 367. 368. 369. 370. 371. 372. 373. 374. 375. 376. 377. 378. 379. 380. 381. 382. 383. 384. 385. 386. 387. 388. 389. 390. 391. 392. 393. 394. 395. 396. 397. 398. 399. 400. 401. 402. 403. 404. 405. 406. 407. 408. 409. 410. 411. 412. 413. 414. 415. 416. 417. 418. 419. 420. 421. 422. 423. 424. 425. 426. 427. 428. 429. 430. 431. 432. 433. 434. 435. 436. 437. 438. 439. 440. 441. 442. 443. 444. 445. 446. 447. 448. 449. 450. 451. 452. 453. 454. 455. 456. 457. 458. 459. 460. 461. 462. 463. 464. 465. 466. 467. 468. 469. 470. 471. 472. 473. 474. 475. 476. 477. 478. 479. 480. 481. 482. 483. 484. 485. 486. 487. 488. 489. 490. 491. 492. 493. 494. 495. 496. 497. 498. 499. 500. 501. 502. 503. 504. 505. 506. 507. 508. 509. 510. 511. 512. 513. 514. 515. 516. 517. 518. 519. 520. 521. 522. 523. 524. 525. 526. 527. 528. 529. 530. 531. 532. 533. 534. 535. 536. 537. 538. 539. 540. 541. 542. 543. 544. 545. 546. 547. 548. 549. 550. 551. 552. 553. 554. 555. 556. 557. 558. 559. 560. 561. 562. 563. 564. 565. 566. 567. 568. 569. 570. 571. 572. 573. 574. 575. 576. 577. 578. 579. 580. 581. 582. 583. 584. 585. 586. 587. 588. 589. 590. 591. 592. 593. 594. 595. 596. 597. 598. 599. 600. 601. 602. 603. 604. 605. 606. 607. 608. 609. 610. 611. 612. 613. 614. 615. 616. 617. 618. 619. 620. 621. 622. 623. 624. 625. 626. 627. 628. 629. 630. 631. 632. 633. 634. 635. 636. 637. 638. 639. 640. 641. 642. 643. 644. 645. 646. 647. 648. 649. 650. 651. 652. 653. 654. 655. 656. 657. 658. 659. 660. 661. 662. 663. 664. 665. 666. 667. 668. 669. 670. 671. 672. 673. 674. 675. 676. 677. 678. 679. 680. 681. 682. 683. 684. 685. 686. 687. 688. 689. 690. 691. 692. 693. 694. 695.
результат: ,1,18,33,50,60,54,64,47,62,56,39,24,7,13,3,9,26,41,58,52,35,25,10,4,19,2,17,11,5,20,14,8,23,40,55,61,51,57,42,59,49,34,44,29,46,63,48,31,16,6,12,27,37,43,53,36,30,45,28,22,32,38,21,15, 11-ки у меня еще нету... возможно, её WITH бы помог обойтись меньшим количеством кода? ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2012, 22:53 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
на всякий - я этот запрос вручную не набирал :) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2012, 23:03 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
оказывается, 11g не любит GROUP BY и аналитику в RECURSIVE WITH с UNION ALL вываливается ORA-32486 а так бы всё красиво :) Код: plsql 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 00:51 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Добил-таки одним запросом :) Код: plsql 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.
для ОРакл 11XE ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 01:18 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Ну ты и демон. Ладно завтра проверю. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 01:37 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxДобил-таки одним запросом :) .. для ОРакл 11XE а на результат с какой стороны смотреть? Код: plsql 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:30 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, номера полей при обходе12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:33 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxorawish, номера полей при обходе1t2t3t4t5t6t7t89t10t11t12t13t14t15t1617t18t19t20t21t22t23t2425t26t27t28t29t30t31t3233t34t35t36t37t38t39t4041t42t43t44t45t46t47t4849t50t51t52t53t54t55t5657t58t59t60t61t62t63t64 ага! теперь понятно :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:38 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymx, чесслово - я не нарочно. это цитирование обалдело :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:43 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishandreymx, чесслово - я не нарочно. это цитирование обалдело :)та мы сами такие :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:44 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
как оказалось, 11g вполне достаточно, чтобы таки решить задачу про все решения тупым перебором. как то грустно даже ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:05 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, Аудитория замерла в ожидании. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:06 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawish, Аудитория замерла в ожидании. после 25-го хода количество вариантов позиции начинает уверенно падать. пока - это всё, что могу сказать. а полный расклад обязательно будет, но чуть позже. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:11 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Эээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:25 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonЭээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче. не силён я в фольклоре. о чем вы? ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:33 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishmaytonЭээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче. не силён я в фольклоре. о чем вы? А забудь, проехали. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 23:02 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
быстро сказка сказывается, но как всегда дело делается дотолкал я таки в гору этот паровоз. и .. получил, таки от оракла значение, которое и так знал - http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%85%D0%BE%D0%B4%D0%B5_%D0%BA%D0%BE%D0%BD%D1%8F Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 (спасибочки предыдущим сетевым и прочим исследователям, а также википедии) четыре картинки (маслом) чего это стоило на (сугубо одной ноде от x2:2 1/4) 1) спейса - чтобы хранить все результаты (причем с учетом, что использовалась compress for query high) надо ~4.9 Tb. но, поскольку всё хранить не надо, а достаточно хранить лишь два шага (из энного считается еэплюспервый), то ,в пике (35 ход) это "всего" 825 Gb ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2012, 16:24 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
2) времени (тут мы понимаем, что один шаг состоит из 64/2 = 32 полей) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2012, 16:26 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
4) ну и, собственно, результат ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2012, 16:29 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%85%D0%BE%D0%B4%D0%B5_%D0%BA%D0%BE%D0%BD%D1%8F Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532dbms_photoshopТри минуты гугления привели к: 33,439,123,484,294 .Как же все-таки банально описание того, что процитированная мной цифра неправильная. http://en.wikipedia.org/wiki/Talk%3AKnight%27s_tour Yes, that's the entry, and I agree it's not completely clear. It claims "Loebbing and Wegener give 33,439,123,484,294 for the 8 X 8 board. The value given here is due to B. McKay and agrees with that given by Wegener in his book.". Reading Loebbing and Wegener gives the figure 33,439,123,484,294 (closed, undirected), but it also claims that it's wrong, because 33,439,123,484,294 is not divisible by 4 . It seems to me that the Sloane page is saying that 13,267,364,410,532 is the corrected figure for 33,439,123,484,294, and is therefore the correct number of closed, undirected 8x8 knight's tours. Wolfram's Mathworld agrees with the 13,267,364,410,532 figure, and they cite [Wegener, I. Branching Programs and Binary Decision Diagrams. Philadelphia, PA: SIAM, 2000] which is a book [ISBN 0-898-71458-3]. I don't have the book, but at this point I think we've got enough verifiability, so I'm going ahead. Until a wiki-author reads that book, I think we don't know the number of non-closed tours. Mathworld simply quotes the figure from the paper which gives the wrong figure for the number of closed tours, which must be highly suspect. Adam1729 07:23, 12 April 2007 (UTC) 13,267,364,410,532 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 02:14 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, да, симметрия - существенна для этой задачи. так, очевидно, что решение для количества всех нециклических траекторий может быть получено как сумма 10 расчетов - (например) с начальных полей a1,b1,b2,c1-c3,d1-d4, разумеется, с учетом соответствующего симметрии каждого поля веса. также, для полей большой диагонали (a1,b2,c3,d4) симметрия позволяет вдвое (т.е. диагонально) ограничить и позиции второго хода. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 03:23 |
|
|
start [/forum/topic.php?fid=52&msg=37749200&tid=1881402]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
40ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
62ms |
get tp. blocked users: |
2ms |
others: | 280ms |
total: | 434ms |
0 / 0 |