• ↓
  • ↑
  • ⇑
 
Записи с темой: algorithms (список заголовков)
13:29 

How to find angle between two points?

Vi Veri Veniversum Vivus Vici
Best explanation ever: mathforum.org/library/drmath/view/61081.html

"I'll call the two points (x1,y1)
and (x2,y2).

x2 = x1 + cos(a * (pi / 180)) * u
y2 = y1 + sin(a * (pi / 180)) * u

Subtract the starting point coordinates:

x2 - x1 = cos(a * (pi / 180)) * u
y2 - y1 = sin(a * (pi / 180)) * u

Divide the second equation by the first:

(y2-y1)/(x2-x1) = (sin(a*pi/180)*u)/(cos(a*pi/180)*u)

What is sin/cos? It's the tangent.

(y2-y1)/(x2-x1) = tan(a*pi/180)

We can find the angle by taking the inverse tangent (arctan) of both
sides:

a*pi/180 = arctan((y2-y1)/(x2-x1))

a = 180/pi * arctan((y2-y1)/(x2-x1))"

@темы: Algorithms

17:42 

All permuations of array of arrays (and even more nested arrays)

Vi Veri Veniversum Vivus Vici
We can to implement this in Javasсript like:



  1. function printTree(t, index, r, delim) {
  2. var out = [],
  3. prefix, res;
  4. r = r || '';
  5. delim = delim || ' ';
  6. index = index || 0;
  7. if (index < t.length) {
  8. t = t.map(function(el) {
  9. return el instanceof Array ? el : [el];
  10. });
  11. prefix = r ? r + delim : '';
  12. for (var i = 0; i < t[index].length; i++) {
  13. if (t[index][i] instanceof Array) {
  14. res = printTree(t[index][i], 0, r, delim);
  15. } else {
  16. res = [prefix + t[index][i]];
  17. }
  18. for (var j = 0; j < res.length; j++) {
  19. out = out.concat(printTree(t, index + 1, res[j], delim));
  20. }
  21. }
  22. } else {
  23. return [r];
  24. }
  25. return out;
  26. }
  27. var tests = [
  28. [1, 2, 3],
  29. [1, [2, 3]],
  30. [
  31. [1, 2], 3
  32. ],
  33. [
  34. [1, 2],
  35. [3, 4]
  36. ],
  37. [
  38. [1, 2],
  39. [3, [4, 5], 6]
  40. ],
  41. [1, [2, [3, [4, 5]]]],
  42. [
  43. [1, 2],
  44. [
  45. [3, [4, 5, 6]], 7
  46. ]
  47. ],
  48. [
  49. [1, 2],
  50. [
  51. [3, [4, 5, 6]], 7
  52. ], 8
  53. ],
  54. [
  55. 1,
  56. [
  57. 2,
  58. [
  59. 3,
  60. [
  61. 4,
  62. [5, 6]
  63. ],
  64. 7
  65. ],
  66. 8
  67. ],
  68. 9
  69. ],
  70. [
  71. 1,
  72. [
  73. 2,
  74. [
  75. 3,
  76. [
  77. [
  78. 4,
  79. [5, 6]
  80. ]
  81. ],
  82. 7
  83. ],
  84. 8
  85. ],
  86. 9
  87. ]
  88. ];
  89. for (var i = 0; i < tests.length; i++) {
  90. print(printTree(tests[i]).join('\n'));
  91. print('\n')
  92. }




As you can see, on each iteration we "increment" accumulator with string, and returns whole string when recursion is over.







You can check it in action at: ideone.com/tP5KTC

@темы: JavaScript, algorithms, permutations

02:59 

Fibonacci modulo search

Vi Veri Veniversum Vivus Vici
  1. import sys
  2.  
  3. s = sys.stdin.readline().split(" ")
  4. n = int(s[0])
  5. m = int(s[1])
  6.  
  7. a = 0
  8. b = 1
  9. f = 1
  10. mem = [a, b]
  11.  
  12. for c in range(2, n+1):
  13. f = (a + b) % m
  14. a = b
  15. b = f
  16. if a == 0 and f == 1:
  17. mem.pop()
  18. break
  19. else:
  20. mem.append(f)
  21.  
  22. pos = n % len(mem)
  23. print(mem[pos])


Online example here: ideone.com/6pl4AR

@темы: Python, Algorithms

23:26 

Задачка от Яндекса; Longest subarayy with equal count of 0 and 1

Vi Veri Veniversum Vivus Vici
Дан массив длины n из нулей и единиц. Найдите в нём подмассив макисмальной длины, в котором количество единиц равно количеству нулей. Ограничения: O(n) по времени и O(n) по дополнительной памяти.

  1. function getLongest(s) {
  2. var begin = 0,
  3. finish = 0,
  4. len = 0,
  5. b = {},
  6. sum = 0,
  7. i,
  8. n = s.length;
  9. prefix,
  10. padding = '',
  11. cursor;
  12. for (i = -n; i < n; i++) {
  13. b[i] = null;
  14. }
  15. b[0] = -1;
  16. for (i = 0; i < n; i++) {
  17. sum += (s[i] == 1 ? 1 : -1);
  18. if (b[sum] == null) {
  19. b[sum] = i;
  20. console.log('for sum = ' + sum + ' index = ' + i);
  21. } else {
  22. console.log('for sum = ' + sum + ' at index = ' + i + ' b = ' + b[sum]);
  23. if (len < i - b[sum]) {
  24. begin = b[sum] + 1;
  25. finish = i;
  26. len = i - b[sum];
  27. console.log('begin = ' + begin + ' finish = ' + finish + ' len = ' + len);
  28. }
  29. }
  30. }
  31. if (begin === finish) {
  32. console.log('No subarray');
  33. return;
  34. }
  35. prefix = '['+begin+':'+finish+'] = ';
  36. for (i = 0; i < prefix.length + s.length; i++) {
  37. cursor = i - prefix.length;
  38. padding += (cursor === begin || cursor === finish) ? '^' : ' ';
  39. }
  40. console.log(prefix + s);
  41. console.log(padding)
  42. console.log(padding.substr(0, prefix.length + begin) + s.substr(begin, finish - begin + 1));
  43. }
  44. (function(tests) {
  45. var i, j, s, len;
  46. for (i = 0; i < tests; i++) {
  47. len = Math.round(Math.random() * 10) + 1;
  48. s = '';
  49. for (j = 0; j < len; j++) {
  50. s += Math.round(Math.random());
  51. }
  52. console.log(s);
  53. getLongest(s);
  54. }
  55. })(3);

@темы: Algorithms, JavaScript, PHP

Small Coder Blog

главная