Guest User

Untitled

a guest
Jun 20th, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. <?php
  2.  
  3. /*
  4. Нахождение формулы решения.
  5. Пусть у нас есть N точек на одной прямой и M - на другой.
  6. отрезок Отр_N1_M1 не пересекается ни с какими отрезками вообще,
  7. отрезок Отр_N1_M2 пересекается (N - 1) раз (все отрезки от точек N2 до NN в точку M1)
  8. отрезок Отр_N1_M3 пересекается 2 * (N - 1) раз (все отрезки от точек N2 до NN в 2 точки на
  9. противоположной стороне - M1 и M2).
  10. И так далее.
  11. Таким образом, сумма точек пересечения всех отрезков, выходящих из точки N1 равна:
  12. (N - 1) + 2 * (N - 1) + 3 * (N - 1) + .... (M - 1)(N - 1) = (N - 1) * (M * (M - 1) / 2)
  13. Если обозначить функцию f(n, m) - как требуемый результат для количества точек n и m,
  14. то
  15. f(n, m) = (n - 1) * (m * (m - 1) / 2) + f(n - 1, m) [1]
  16.  
  17. f(n - 1, m) аналогично разворачивается в:
  18.  
  19. f(n - 1, m) = (n - 2) * (m * (m - 1) / 2) + f(n - 2, m)
  20.  
  21. Подставляя это выражение в формулу выше [1] и развертывая формулу дальше получаем
  22. итоговую формулу:
  23.  
  24. f(n, m) = (n - 1 + n - 2 + .... + 1) * m * (m - 1) / 2 =
  25. (n * (n - 1) / 2) * (m * (m - 1) / 2)
  26. */
  27.  
  28. function task103($n, $m) {
  29. return ($n * ($n - 1) / 2) * ($m * ($m - 1) / 2);
  30. }
  31.  
  32.  
  33. function test($n, $m) {
  34. printf("%s, %s => %s\n", $n, $m, task103($n, $m));
  35. }
  36.  
  37.  
  38. foreach([[2, 3], [1, 1], [1, 2], [2, 2], [1000, 1000]] as $data) {
  39. test($data[0], $data[1]);
  40. }
  41.  
  42. /** результаты тестов
  43. 2, 3 => 3
  44. 1, 1 => 0
  45. 1, 2 => 0
  46. 2, 2 => 1
  47. 1000, 1000 => 249500250000
  48. */
Add Comment
Please, Sign In to add comment