Поиск узлов из простых чисел

Функция получения случайных чисел

Сейчас мы покажем генератор псевдослучайных чисел. Это означает, что фактическая последовательность чисел предсказуема, но они разбросаны довольно равномерно в пределах возможного диапазона значений.

Схема начинает с числа, называемого "зерно". Она использует его для создания нового числа, которое становится новым зерном. Затем новое зерно можно использовать для создания более нового зерна и т.д. Чтобы эта схема работала, функция случайных чисел должна помнить зерно, которое она использовала при последнем вызове. Отметим, здесь нужно использовать статическую переменную!

/* Первая версия функции rand()*/

rand()

{

static int randx = 1;

randx = (randx * 25173 + 13849)%65536;

/* магическая формула */

return(randx);

}

Статическая переменная randx начинает со значения 1 и изменяется при помощи магической формулы каждый раз при вызове функции. Результатом в нашей системе является число, находящееся в диапазоне -32768 до 32767. Системы с разной длиной переменной типа int будут давать различные результаты.

Проверим работу функции при помощи этого простого драйвера:

/*драйвер 1 функции rand() */

main()

{

int count;

for(count = 1; count <= 5; count++)

printf(" %d\n",rand());

}

Получим результат:

-26514

-4449

-20531

Эта последовательность чисел выглядит довольно случайной. Запустим драйвер еще раз. Теперь имеем

-26514

-4449

-20531

Получилось абсолютно то же самое. Это и есть псевдоэффект. Каждый раз, когда работает основная программа, мы начинаем с одного и того же значения зерна, равного 1. Можно обойти эту проблему, введя вторую функцию srand(), которая позволяет вновь устанавливать зерно в начальное значение. Хитрость заключается в том, чтобы сделать randx внешней статической переменной, известной только функциям rand() и srand(). Эти две функции нужно хранить в своем собственном файле и компилировать этот файл отдельно. Вот модификатор программы:

/* Файл для rand() и srand() */

static int randx = 1;

rand()

{

randx = (randx * 25173 + 13849) % 65536;

return(randx);

}

srand(x)

unsigned x;

{

randx = x;

}

Используем другой драйвер:

/* драйвер 2 функции rand() */

main()

{

int count;

int seed;

printf(" Введите свое значение зерна.\n");

scanf("%d", & seed);

srand(seed);

/* установите зерно в начальное значение */

for(count = 1; count <= 5; count++)

printf("%\n",rand());

}

Программа проработала один раз:

Введите свое значение зерна.

-26514

-4449

-20531

Используя значение 1 для переменной seed, получаем те же значения, что и прежде. Введем значение 2 и посмотрим, что получится:

-1858

-30417

-16204

Мы получили другую последовательность чисел.

Всякий, кто изучает простые числа, бывает очарован ими и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно. Найти очередное простое число так легко, разложение на простые сомножители - такое естественное действие! Почему же тогда простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим их?

Какой-то порядок в простых числах, несомненно, есть. Простые числа можно отсеять от составных решетом Эратосфена. Начнем с того, что 2 - простое число. Теперь выбросим все большие четные числа (делящиеся на 2). Первое из уцелевших за двойкой чисел, 3, также должно быть простым. Удалим все его кратные, останется 5. После удаления кратных пяти останется 7. Будем продолжать в том же духе. Все числа, прошедшие через решето, будут простыми. Это регулярная, хотя и медленная процедура находит все простые числа. Оказывается, что все известные методы построения таблицы простых чисел - не что иное, как вариации метода решета. Эйлер придумал формулу x2+x+41. Для всех x от нуля до 39 эта формула дает простые числа. Однако, никакая полиномиальная формула не может давать подряд бесконечный ряд простых чисел. Формула Эйлера терпит фиаско при x=40. Закономерность появления простых чисел проявляется, когда целые числа отображаются на плоскость (или в пространство).

Напишем программу, которая отображает целые числа на плоскость некоторым регулярным образом, и отмечает на рисунке места, где находятся простые числа:

// Построить матрицу А(15x15)таким образом:

// А(7,7)=1, затем, по спирали против

// часовой стрелки, увеличивая значение

// очередного элемента на единицу и

// выделяя все простые числа красным цветом

// заполнить матрицу

#include <stdio.h>

#include <conio.h>

void main(void)

{

clrscr();

int mas[15][15];

int n=1,x=6,y=6,k=1;

int i,j;

while(1){

mas[x][y]=k++;

switch(n){

case 1: x++;break;

case 2: y--;break;

case 3: x--;break;

case 4: y++;break;

}

if(x==15) break;

if(x==y && x<6) n=4;

else if(x+y==12 && x<6) n=1;

else if(x+y==12 && x>6) n=3;

else if(x==y+1 && x>6) n=2;

}

for(i=0;i<15;i++)

{

for(j=0;j<15;j++)

{

textcolor(12);

if(mas[j][i]>2)

for(k=2;k<mas[j][i];k++)

if(mas[j][i]%k==0) textcolor(15);

cprintf("%3d ",mas[j][i]);

}

printf("\n");

}

getch();

}

Дата добавления: 2014-01-05