Меню сайта

Статистика

Онлайн всего: 1

Гостей: 1

Пользователей: 0

Форма входа

Лекция 16

Содержание

Функция получения случайных чисел
Поиск узлов из простых чисел
Матрица инцидентности
Структуры данных

Стеки
Очереди
Связанные списки

Все операции со стеком
Подведем итог

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

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

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

/* Первая версия функции 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( ));
}

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

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

Получилось абсолютно то же самое. Это и есть псевдоэффект. Каждый раз, когда работает основная программа, мы начинаем с одного и того же значения зерна, равного 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("%d\n",rand( ));
}

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

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

1
-26514
-4449
20196
-20531
3882

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

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

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

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

Какой-то порядок в простых числах, несомненно, есть. Простые числа можно отсеять от составных решетом Эратосфена. Начнем с того, что 2 - простое число. Теперь выбросим все большие четные числа (делящиеся на 2). Первое из уцелевших за двойкой чисел, 3, также должно быть простым. Удалим все его кратные, останется 5. После удаления кратных пяти останется 7. Будем продолжать в том же духе. Все числа, прошедшие через решето, будут простыми. Это регулярная, хотя и медленная процедура находит все простые числа. Оказывается, что все известные методы построения таблицы простых чисел - не что иное, как вариации метода решета. Эйлер придумал формулу x²+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();
}

Матрица инцидентности

Матрица I(G) размером n x m (n - число вершин, m - число ребер/дуг графа G), (i,j)-й элемент, которой равен 1, если вершина n_i инцидентна ребру e_ij в неориентированном графе или если n_i есть начало дуги e_j равен -1, если вершина n_i есть конец дуги e_j (только для ориентированных графов), и равен 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();
}

Структуры данных

Решение комбинаторных задач предполагает выделение структур сложного типа с их последующей реализацией средствами выбранного языка программирования. При этом структура данных может не зависеть от конкретных языковых конструкций (абстрактная структура данных).

Под структурой данных понимают совокупность элементов фиксированных типов и набор базисных операций, определяющих организацию и способ обработки данных.

Рассмотрим некоторые основные структуры данных.

Стеки

Стеком называется структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом 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];
```

Очереди

Очередь - одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала (head) и конца (tail) очереди в соответствии с правилом FIFO (first-in, first-out - первым введен, первым выведен).

Начальная установка:
```
head=1; tail=1;
```
Добавление элемента:
```
queue[tail]=x; tail=tail+1;
if(tail>qd) tail=1;
```
Здесь qd - размерность очереди.

Исключение элемента:

x=queue[head]; head=head+1;
if(head>qd) tail=1;

Проверка переполнения очереди и включение в нее элемента:
```
temp=tail+1;
if(temp=head)
{Переполнение}
else {queue[tail]=x; tail=temp}
```

Проверка наличия элементов и исключение элемента х:

if(head==tail) { очередь пуста}
else{ x=queue[head]; head=head+1;
if(head>qd) head=1;}

Отметим, что, при извлечении элемента из очереди, все элементы могут также перемещаться на один шаг к ее началу.

Связанные списки

Связанный список представляет собой структуру данных, состоящую из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением null. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи).

Приведем основные базисные операции для работы с однонаправленным связанным списком.

Включение элемента после элемента p:
```
link[q]=link[p];
link[p]=q;
```
Здесь q - индекс элемента, который должен быть вставлен в список после элемента с индексом.
Исключение преемника элемента x:
```
if(link[x] != NULL) link[x]=link[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;
}

Подведем итог

Следует обратить внимание на самый существенный момент: программы нужно проектировать, а не создавать их методом проб и ошибок. Мы должны внимательно подумать о форме и содержании ввода и вывода для программы. Необходимо разделить программу на хорошо определенные задачи, затем раздельно запрограммировать, принимая во внимание их взаимодействие друг с другом. Идея заключается в достижении модульности. Если необходимо, разбивайте модули на еще более мелкие модули. Используйте функции для повышения степени модульности и простоты программы.

При проектировании программы попытайтесь предвидеть, что может идти неправильно, и программируйте, исходя из этого. Используйте локализацию ошибок, чтобы контролировать действия в местах потенциальных затруднений, или, по крайней мере, предупреждать пользователя, что может возникнуть осложнение. Гораздо лучше дать пользователю еще одну возможность ввести данные, чем продолжать выполнять программу и прийти к аварийной ситуации. Если создается функция, сначала определите, как она будет взаимодействовать с вызывающей программой. Решите также, какая информация будет входить в нее, а какая - выходить. Какими должны быть аргументы? Если вы примете во внимание все эти параметры, то можете обратить внимание на работу самой функции. Используйте эти идеи, и ваша программа будет более надежной и менее подверженной аварийным ситуациям. Вы получите тело функции, которое сможете применять в других программах. Программирование в таком случае потребует меньше времени. Не забывайте о классах памяти. Переменные можно определять вне функции. В этом случае их называют внешними или глобальными и они доступны более чем для одной функции. Переменные, определенные внутри функции, являются локальными для нее, и не известны другим функциям. Если можно, используйте автоматическую разновидность локальных переменных. Они охраняют переменные одной функции от взаимодействия других функций.

Поиск