Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
steam13
1 / 1 / 1
Регистрация: 24.02.2012
Сообщений: 32
1

Генерация двух чисел для дальнейшего нахождения их НОДа

09.06.2013, 23:04. Просмотров 672. Ответов 2
Метки нет (Все метки)

Здравствуйте.
Пишу тренажер по дискретной математике. И нуждаюсь в алгоритме генерации двух чисел для дальнейшего нахождения их НОДа.
Пробовал и что то подобное, но частенько вылетают тривиальные решения =(
Нужно чтобы было от 4 до 6 шагов. Ищется НОД по алгоритму Евклида.
Пока надумал только идти от обратного. Т.е. генерирую нод - выполняю шаги - получаю два числа

Java
1
2
3
4
  
int k = 2+ generator.nextInt(12);               // НОД
int n1 = k*(generator.nextInt(12) + 10);
int n2 = k*(generator.nextInt(11) + 7);
Подскажите пожалуйста алгоритм. Можно сразу на каком либо языке программирования, там разберусь.
Заранее спасибо, товарищи))
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2013, 23:04
Ответы с готовыми решениями:

Подпрограммы. Составить программу нахождения наибольшего общего делителя нескольких чисел, используя функцию нахождения НОД двух чисел
Задачи нужно решить с помощью процедур 1 Составить программу нахождения наибольшего общего...

Найти набольший общий делитель чисел A, B, C, создав процедуру для нахождения НОД двух натуральных чисел
Найти набольший общий делитель чисел A, B, C, создав процедуру для нахождения НОД двух натуральных...

Метод min(a,b) для нахождения минимального из двух чисел
пожалуйста, помогите разработать метод min(a,b) для нахождения минимального из двух чисел....

Разработать метод для нахождения минимального из двух чисел
Разработать метод min (a,b) для нахождения минимального из двух чисел. Вычислить с помощью него...

Разработать функцию min(a,b) для нахождения минимального из двух чисел
Вычислить с помощью него минимальное значение из четырех x,y,z,v.

2
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,021
Записей в блоге: 22
10.06.2013, 19:48 2
Не думаю, что мой ответ будет очень полезным. Я исходил из принципа «сгенерировать все варианты и случайным образом выбрать один».

Первый заход
Написал по-быстрому программу, которая генерирует массив (в JavaScript / Haskell нотации) возможных пар (x,y), для которых НОД вычисляет ровно за n шагов, 2<x,y<limit.
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
file = "/home/ml/data.js"
a = appendFile file
 
gcdn :: Int -> Int -> Int
gcdn x y = case compare x y of
    EQ -> 0
    LT -> succ$ gcd x (y-x)
    GT -> succ$ gcd (x-y) y
 
getAllVariants :: Int -> Int -> [(Int, Int)]
getAllVariants limit n = [ (x,y) | x <- [1..limit], y <- [1..limit], x<y, gcdn x y == n ]
 
main :: IO ()
main = let r = getAllVariants 50 in do
    --writeFile file ""
    a "var x = [\n"
    sequence_ [ a$ "\t" ++ (show$ map fst$ r n) ++ ",\n" | n <- [0..10] ]
    a "[]];\nvar y = [\n"
    sequence_ [ a$ "\t" ++ (show$ map snd$ r n) ++ ",\n" | n <- [0..10] ]
    a "[]];"
Результат: файл data.js
Javascript
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
var x = [
    [],
    [],
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,20,20,20,20,20,20,20,20,20,20,20,20,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,26,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,30,30,30,30,30,30,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,32,32,32,32,32,32,32,32,32,33,33,33,33,33,33,33,33,33,33,33,34,34,34,34,34,34,34,34,35,35,35,35,35,35,35,35,35,35,36,36,36,36,36,37,37,37,37,37,37,37,37,37,37,37,37,37,38,38,38,38,38,38,39,39,39,39,39,39,39,39,40,40,40,40,41,41,41,41,41,41,41,41,41,42,42,43,43,43,43,43,43,43,44,44,44,45,45,45,46,46,47,47,47,48,49],
    [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,4,4,4,4,4,4,4,4,4,4,4,4,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,8,8,8,8,8,8,8,8,8,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,12,12,12,12,12,12,12,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,16,16,16,16,16,16,16,16,16,18,18,18,18,18,18,18,18,18,18,18,20,20,20,20,20,20,22,22,22,22,22,22,22,22,22,22,22,22,22,24,24,24,24,24,26,26,26,26,26,26,26,26,26,26,26,26,28,28,28,28,28,30,30,30,30,30,32,32,32,32,32,34,34,34,34,34,34,34,34,36,36,36,38,38,38,38,38,38,40,40,42,42,42,44,44,46,46,48],
    [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,6,6,6,6,6,6,6,9,9,9,9,9,9,9,9,9,12,12,12,12,12,12,15,15,15,15,15,15,15,15,15,18,18,18,21,21,21,21,21,21,21,21,24,24,24,24,27,27,27,27,27,30,30,33,33,33,33,33,36,39,39,39,42,45],
    [4,4,4,4,4,4,4,4,4,4,4,8,8,8,8,8,12,12,12,12,12,12,16,16,16,16,20,20,20,20,20,20,24,24,28,28,28,28,28,32,32,36,36,40,44],
    [5,5,5,5,5,5,5,5,5,10,10,10,10,15,15,15,15,15,20,20,20,25,25,25,25,30,35,35,35,40,45],
    [6,6,6,6,6,6,6,12,12,12,18,18,18,18,24,24,30,30,30,36,42],
    [7,7,7,7,7,7,14,14,14,21,21,21,28,28,35,35,42],
    [8,8,8,8,8,16,16,24,24,32,40],
    [9,9,9,9,18,18,27,27,36],
[]];
var y = [
    [],
    [],
    [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,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,8,9,10,11,12,13,15,16,17,18,19,20,22,23,24,25,26,27,29,30,31,32,33,34,36,37,38,39,40,41,43,44,45,46,47,48,50,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,28,29,30,31,32,34,35,36,37,38,39,40,41,42,43,45,46,47,48,49,50,13,17,19,23,25,29,31,35,37,41,43,47,49,14,15,16,17,18,19,20,21,22,23,24,25,27,28,29,30,31,32,33,34,35,36,37,38,40,41,42,43,44,45,46,47,48,49,50,15,17,19,23,25,27,29,31,33,37,39,41,43,45,47,16,17,19,22,23,26,28,29,31,32,34,37,38,41,43,44,46,47,49,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,19,23,25,29,31,35,37,41,43,47,49,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,39,40,41,42,43,44,45,46,47,48,49,50,21,23,27,29,31,33,37,39,41,43,47,49,22,23,25,26,29,31,32,34,37,38,40,41,43,44,46,47,50,23,25,27,29,31,35,37,39,41,43,45,47,49,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,47,48,49,50,25,29,31,35,37,41,43,47,49,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49,27,29,31,33,35,37,41,43,45,47,49,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,29,31,33,37,39,41,43,45,47,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,31,37,41,43,47,49,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,33,35,37,39,41,43,45,47,49,34,35,37,38,40,41,43,46,47,49,50,35,37,39,41,43,45,47,49,36,37,38,39,41,43,44,46,47,48,37,41,43,47,49,38,39,40,41,42,43,44,45,46,47,48,49,50,39,41,43,45,47,49,40,41,43,44,46,47,49,50,41,43,47,49,42,43,44,45,46,47,48,49,50,43,47,44,45,46,47,48,49,50,45,47,49,46,47,49,47,49,48,49,50,49,50],
    [4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,6,10,14,18,22,26,30,34,38,42,46,50,8,10,14,16,20,22,26,28,32,34,38,40,44,46,50,10,14,18,22,26,30,34,38,42,46,50,12,14,16,18,22,24,26,28,32,34,36,38,42,44,46,48,14,22,26,34,38,46,50,16,18,20,22,24,26,30,32,34,36,38,40,44,46,48,50,18,22,26,30,34,38,42,46,50,20,22,26,28,32,34,38,40,44,46,50,22,26,34,38,42,46,24,26,28,30,32,34,36,38,40,42,46,48,50,26,34,38,46,50,28,30,32,34,36,38,40,42,44,46,48,50,30,34,38,46,50,32,34,38,44,46,34,38,42,46,50,36,38,40,42,44,46,48,50,38,46,50,40,42,44,46,48,50,42,46,44,46,50,46,50,48,50,50],
    [6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,9,15,21,27,33,39,45,12,15,21,24,30,33,39,42,48,15,21,27,33,39,45,18,21,24,27,33,36,39,42,48,21,33,39,24,27,30,33,36,39,45,48,27,33,39,45,30,33,39,42,48,33,39,36,39,42,45,48,39,42,45,48,45,48],
    [8,12,16,20,24,28,32,36,40,44,48,12,20,28,36,44,16,20,28,32,40,44,20,28,36,44,24,28,32,36,44,48,28,44,32,36,40,44,48,36,44,40,44,44,48],
    [10,15,20,25,30,35,40,45,50,15,25,35,45,20,25,35,40,50,25,35,45,30,35,40,45,35,40,45,50,45,50],
    [12,18,24,30,36,42,48,18,30,42,24,30,42,48,30,42,36,42,48,42,48],
    [14,21,28,35,42,49,21,35,49,28,35,49,35,49,42,49,49],
    [16,24,32,40,48,24,40,32,40,40,48],
    [18,27,36,45,27,45,36,45,45],
[]];

Кроме этого, для демонстрации создадим файл main.html
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<html>
<head>
<script type="text/javascript" src="data.js"></script>
<!-- в файле rand.js описывается function Poisson(lambda) -->
<script type="text/javascript" src="rand.js"></script>
<script type="text/javascript">
function getPair() {
  var r;
  do {
    r = Poisson(5);
  } while( ! x[r] || x[r].length == 0 );
  var index = Math.floor(Math.random() * x[r].length);
  return [x[r][index], y[r][index]];
}
function ButtonClick() {
  alert(getPair());
}
</script>
</head>
<body>
<input type=button onclick="ButtonClick();" value="Click it">
</body>
</html>

Более красивый вариант
Всё переписал под JS. Получилось так.
Файл script.js
Javascript
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
/* определяет число шагов в цепочке Эвклида */
function gcdn(x, y) {
  return x == y ? 0 : 1 + ( x > y ? gcdn(x-y, y) : gcdn(x, y-x) );
}
 
function getAllVariants(n,limit) {
  var vs = [];
  for(var x = 2; x < limit; ++x)
    for(var y = x+1; y < limit; ++y)
      if( gcdn(x, y) == n )
        vs.push([x, y]);
  return vs;
} 
 
function randomChoice(a) { return a[Math.floor(Math.random()*a.length)]; }
 
function getPair() {
  var r;
  do {
    r = Poisson(5);
    // можно поменять на другой генератор
  } while( r < 2 );
  var v = getAllVariants(r, 50);
  return randomChoice(v);
}
 
/* формируем цепочку */
function solve(x, y) {
  var solution = "("+x+","+y+")";
  while(x != y) {
      if( x > y ) x -= y; else y -= x;
      solution += " -> ("+x+","+y+")";
  }
  return solution;
}
 
function ButtonClick() {
  var p = getPair();
  alert(solve(p[0], p[1]));
}
Файл main.html
HTML5
1
2
3
4
5
6
7
8
9
10
<html>
<head>
<!-- в файле rand.js описывается function Poisson(lambda) -->
<script type="text/javascript" src="rand.js"></script>
<script type="text/javascript" src="script.js"></script>
</head>
<body>
<input type=button onclick="ButtonClick();" value="Click it">
</body>
</html>

В обоих примерах на первом шаге генерируется длина цепочки Эвклида, как случ. величина с распределением Пуассона. Матожидание и дисперсия — основной параметр — полагается равным 5.
rand.js
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
/* файл rand.js */
function Poisson(l) {
    var r = Math.random();
    var k = 0;
    var s = 0;
    var x = Math.exp(-l);
    while( s < r ) {
        ++k;
        s += x;
        x *= l / k;
    }
    return --k;
}

В принципе, можно использовать не Пуассон, а равномерное распределение на {4,5,6}.
Также можно поменять ghcn. Я полагал, что НОД(6,8) считается так: (6,8) -> (6,2) -> (4,2) -> (2,2). Можно считать быстрее: (6,8) -> (6,2) -> (2,2). То есть на каждом шаге не вычитать только само число, а делить с остатком. Тогда будет что-то такое
Javascript
1
2
3
function gcdn(x, y) {
  return x > y ? gcdn(y, x) : ( y % x == 0 ? 0 : 1 + gcdn(x, y%x) );
}
0
steam13
1 / 1 / 1
Регистрация: 24.02.2012
Сообщений: 32
10.06.2013, 20:09  [ТС] 3
Спасибо)
Буду разбираться в вашем коде.
Сам сделал без каких либо мат.фундаментов.
Просто генерировал 2 числа - по шагам считал их НОД - если шагов меньше 5, то генерировал новые числа
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2013, 20:09

Использовать директиву #define для нахождения наименьшего из двух чисел
помогите решить, пожалуйста Даны целые числа а и b. Используя директиву #define для нахождения...

Разработать метод min (a,b) для нахождения минимального из двух чисел
Пример: Разработать метод min (a,b) для нахождения минимального из двух чисел. Вычислить с помощью...

Проверьте правильность кода для нахождения НОК двух чисел
static void Main(string args) { //При нахождении НОК использовалось свойство...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru