Функция получения случайных чисел
Сейчас мы покажем генератор псевдослучайных чисел. Это означает, что фактическая последовательность чисел предсказуема, но они разбросаны довольно равномерно в пределах возможного диапазона значений.
Схема начинает с числа, называемого "зерно". Она использует его для создания нового числа, которое становится новым зерном. Затем новое зерно можно использовать для создания более нового зерна и т.д. Чтобы эта схема работала, функция случайных чисел должна помнить зерно, которое она использовала при последнем вызове. Отметим, здесь нужно использовать статическую переменную!
/* Первая версия функции 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 20196 -20531 3882
Эта последовательность чисел выглядит довольно случайной. Запустим драйвер еще раз. Теперь имеем
-26514 -4449 20196 -20531 3882
Получилось абсолютно то же самое. Это и есть псевдоэффект. Каждый раз, когда работает основная программа, мы начинаем с одного и того же значения зерна, равного 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( )); }
Программа проработала один раз:
Введите свое значение зерна.
1 -26514 -4449 20196 -20531 3882
Используя значение 1 для переменной seed, получаем те же значения, что и прежде. Введем значение 2 и посмотрим, что получится:
2 23832 20241 -1858 -30417 -16204
Мы получили другую последовательность чисел.
Матрица инцидентности
Матрица I(G) размером n x m (n - число вершин, m - число ребер/дуг графа G), (i,j)-й элемент, которой равен 1, если вершина ni инцидентна ребру eij в неориентированном графе или если ni есть начало дуги ej равен -1, если вершина ni есть конец дуги ej (только для ориентированных графов), и равен 0 в остальных случаях.
В данной задаче задается граф и строится его матрица инцидентности:
//Построение матрицы инцидентности #include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h> #include <iostream.h> struct elem { int num; /* Номер вершины */ int suns; /* Количество сыновей */ char str[20]; /* Строка с номерами сыновей */ elem *next; /* Указатель на следующую вершину */ } *head, *w1, *w2; int connected(int i, int j) { int k; char *str1; w2 = head; if(i == j) return 0; for(k=1; k<i; k++) w2 = w2->next; if( strchr(w2->str, j) ) return 1; return 0; } void main() { int tops; int i,j,k,l; char *str1; clrscr(); printf("Введите количество вершин \n"); scanf("%d", &tops); head = (elem *)malloc(sizeof(elem)); head->num = 1; head->suns = 0; head->str[0] = '\0'; head->next = NULL; w1 = head; for(i=2;i<=tops;i++) { w2 = (elem *)malloc(sizeof(elem)); w2->num = i; w2->suns = 0; w2->str[0] = '\0'; w2->next = NULL; w1->next = w2; w1 = w2; } w1 = head; for(i=1; i<=tops; i++) { // clrscr(); printf("Введите количество путей из вершины %d\n", i); scanf("%d", &k); for(j=1; j<=k; j++) { printf("Введите связь %d\n", j); scanf("%d", &l); if((l<=0) || (l > tops)) { printf("Такой вершины нет, повторите попытку\n"); l = 0; j--; continue; } w1->str[w1->suns++] = l; w1->str[w1->suns] = '\0'; if(w1->suns == 49) { printf("Слишком много связей !"); exit(1); } } w1 = w1->next; } clrscr(); printf("\n\n Матрица инциндентности :\n"); for(i=1; i<=tops; i++) { printf("\n %d) ", i); for(j=1; j<=tops; j++) { printf("%d ", connected(i, j)); } } printf("\n\n Нажмите любую клавишу..."); getch(); }
Поиск узлов из простых чисел
Всякий, кто изучает простые числа, бывает очарован ими и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно. Найти очередное простое число так легко, разложение на простые сомножители - такое естественное действие! Почему же тогда простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим их?
Какой-то порядок в простых числах, несомненно, есть. Простые числа можно отсеять от составных решетом Эратосфена. Начнем с того, что 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(); }
Стеки
Стеком называется структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO (last-in, first-out - последним введен, первым выведен).
Указатель стека sp (stack pointer) содержит в любой момент времени индекс (адрес) текущего элемента, который является единственным элементом стека, доступным в данный момент времени для работы со стеком (для случая, когда указатель стека всегда задает ячейку, находящуюся непосредственно над его верхним элементом).
Начальная установка:
sp=1; Загрузка элемента х в стек:
stack[sp]=x; sp=sp+1;Извлечение элемента из стека:
sp=sp-1; x=stack[sp];Проверка на переполнения и загрузка элемента в стек:
if(sp<=sd) {stack[sp]=x;sp=sp+1} else// переполнение
Здесь sd - размерность стека.
Проверка наличия элементов и извлечение элемента стека:
if (sp>1){sp=sp-1;x=stack[sp]} //антипереполнениеЧтение данных из указателя стека без извлечения элемента:
x=stack[sp-1];
Структуры данных
Решение комбинаторных задач предполагает выделение структур сложного типа с их последующей реализацией средствами выбранного языка программирования. При этом структура данных может не зависеть от конкретных языковых конструкций (абстрактная структура данных).
Под структурой данных понимают совокупность элементов фиксированных типов и набор базисных операций, определяющих организацию и способ обработки данных.
Рассмотрим некоторые основные структуры данных.
Связанные списки
Связанный список представляет собой структуру данных, состоящую из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением null. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи).
Приведем основные базисные операции для работы с однонаправленным связанным списком.
Включение элемента после элемента p:
link[q]=link[p]; link[p]=q;
Здесь q - индекс элемента, который должен быть вставлен в список после элемента с индексом.
Исключение преемника элемента x:
if(link[x] != NULL) link[x]=[link[x]] else {элемент не имеет преемника}
Отметим, что элемент, следующий в списке за элементом x, называется преемником элемента x, а элемент, расположенный перед элементом x, называется предшественником элемента x. Если элемент x не имеет преемника, то содержащемуся в нем указателю присваивается значение null.
Включение элемента y перед элементом x:
prev=0; while((link[prev]!=null) && (link[prev]!=x)) do prev=link[prev]; if (link[prev]==x) { link[prev]=y; link[y]=x } else { элемент x не найден };
Здесь link[0] является началом списка.
Отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка.
В двунаправленном связанном списке каждый элемент имеет два указателя (succlink - описывает связь элемента с преемником, predlink - с предшественником).
Приведем основные базисные операции для работы с двунаправленным связанным списком.
Включение элемента перед элементом x:
succlink[y]=x; predlink[y]=predlink[x]; succlink[predlink[x]]=y; predlink[x]=y;Включение элемента y после элемента x:
succlink[y]=succlink[x]; predlink[y]=x; predlink[succlink[x]]=y; succlink[x]=y;Исключение элемента x:
predlink[succlink[x]]=predlink[x]; succlink[predlink[x]]=succlink[x];
Пример 1:
/* В список помещаются цифры 1...10 Вводится число 11, сначала вставляется за цифрой 10, затем рвется связь между 3 и 4, между ними вставляется число 11. Пример дает навык работы: - с динамической памятью; - создания абстрактной структуры данных - список и модификации списка; - со структурами данных; - с функциями. */ #include <stdlib.h> #include <string.h> #include <stdio.h> #include <conio.h> #include <math.h> #include <dos.h> struct List { int i; List *next; }; /* структура данных, первое поле для хранения целого, второе поле-адрес в динамической памяти*/ List*head=NULL; /* начальный адрес*/ void Hed(int i) /* функция, которая создает очередной элемент списка */ { if(head==NULL) { head=( List*)malloc(sizeof(List)); head->i=1; head->next=NULL; } else { struct List *p,*p1; p=head; while(p->next!=NULL) p=p->next; p1=new List; p1->i=i; p1->next=NULL; p->next=p1; } } int s=0; void Print(List*p)/* вывод списка на экран */ { printf(" %d",p->i); if(p->next!=NULL)Print(p->next); } void delist()/* освобождение динамической памяти */ { List*p; while(head!=NULL) { p=head; head=head->next; free(p); } } void Vstavka(int i1,int c) /*вставка нового элемента*/ { List*p=head,*p1; while(p->i!=i1) p=p->next; p1=new List; p1->i=c; p1->next=p->next; p->next=p1; } void main()/* вход в программу */ { clrscr();/* очистить экран */ for(int i=1;i<=10;i++) Hed(i);/* создание списка */ Print(head);/* вывод списка на экран */ Vstavka(10,11); printf("\n"); Print(head); Vstavka(3,11); printf("\n"); Print(head); delist(); getch(); }
Все операции со стеком
Структура данных стека. Принципы выборки и записи в стек описаны выше.
// Работа со стеком. Проверка, пуст ли стек. // Добавить в стек. Выбрать из стека. // Стек полон #include <stdio.h> #include <dos.h> #include <iostream.h> #include <Process.H> #include <Stdlib.H> #include <conio.H> #define max_size 200 char s[max_size]; //компоненты стека int next=0; // позиция стека int Empty() { return next==0; } int Full() { return next==max_size; } void Push() { if (next==max_size) { cout<<"Ошибка: стек полон"<<endl;} else { next++;cout<<"Добавлен"<<endl; cout<<"Что поместить в стек?"<<endl; cin >> s[next-1]; } } void OUTst() { int i=0; if (next==0) { cout<<"Cтек пуст"<endl; } else { for(i=0;i<next;i++) cout<<s[i]<<" "<<endl; } } void Clear() { next=0; } Poz() { return next; } void Del() { int a; if (next==0) cout<<"Ошибка: стек пуст"<<endl; else { next--;cout<<"Удален "<<endl; } } void menu() { cout<<"0: распечатать стек"<<endl; cout<<"1: добавить в стек"<<endl; cout<<"2: удалить из стека"<<endl; cout<<"3: узнать номер позиции в стеке"<<endl; cout<<"4: узнать, пуст ли стек"<<endl; cout<<"5: узнать, полон ли стек"<<endl; cout<<"6: очистить стек"<<endl; cout<<"7: выход"<<endl; } main() { char c; clrscr(); textcolor(15); do { menu(); cin >> c; clrscr(); switch (c) { case '0':OUTst();getch();break; case '1':Push();break; case '2':Del();getch();break; case '3':cout<< "Hомер "<<Poz()<<endl;getch();break; case '4':if (Empty()==1) cout<<"Пуст"<<endl; else cout<<"Hе пуст"<<endl;getch();break; case '5':if (Full()==1)cout<<"Полн"<<endl; else cout<<"Hе полн"<<endl;getch();break; case '6':Clear();cout<< "Стек очищен"<<endl;getch();break; case '7':exit(1); } delay(200); } while (c!=7); return 0; }