Шпаргалка по языку СИ. Конспект Лекций «программирование На Языке Высокого Уровня Си» П. Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления
 Скачать 1.25 Mb.
|
|
int main() { cout << "Введите числитель дроби : \r"; cin >> m; cout << "\r\nВведите знаменатель дроби : \r"; cin >> n; ostatki = new int[n+1]; period = new int[n+1]; int d = m, q = n; int r, pos; len = 1; do { r = d % q; ostatki[len] = r; d /= q; period[len] = d; d = 10 * r; len++; } while ((pos = IsInOstatki (r, len/*сколько остатков помещено в массив остатков*/)) == 0); // вывод результатов cout << "дробь= \r\n"; cout << period[1] << ","; for (r = 2; r < len; r++) { cout << period[r]; } cout << "\r\n период = "; for(r = pos + 1; r < len; r++) cout << period[r]; cout << "\r\n"; // освобождение ресурсов delete[] ostatki; delete[] period; system ("pause"); } Результат выполнения программы Введите числитель дроби : 12 Введите знаменатель дроби : 13 дробь 0,923076 период = 923076 Пример 5. Вычисление интервала в днях между двумя датами текущего года. 179 Год високосный, если он делится на четыре без остатка, но если он делится на 100 без остатка, это не високосный год. Однако если он делится без остатка на 400, это високосный год. Таким образом, 2000 г. является особым високосным годом, который бывает лишь раз в 400 лет. #include #include #include #include int main() { int Temp; int DaysInMonth[2][12]= //количество дней в месяцах 0-обычном, 1 - високосном {{31,28,31,30,31,30,31,31,30,31,30,31}, {31,29,31,30,31,30,31,31,30,31,30,31} }; //вводим исходные данные int CurrentYear, Diff, Day1, Day2, Month1, Month2, i, Visokos; printf("\nВведите год : "); scanf("%d",&CurrentYear); printf("Введенный год %d. \n",CurrentYear); //проверяем нависокосный год if(CurrentYear%400==0 || (CurrentYear%4==0 && CurrentYear%100!=0)) { printf("\nВисокосный год!\n\n"); Visokos=1; } else { printf("\nNE Visokosny god!\n\n"); Visokos=0; } do { printf("Введите день 1 (1-31):"); scanf("%d",&Day1); printf("Введите месяц 1 (1-12) :"); scanf("%d",&Month1); } while ((Month1<1||Month1>12)||(Day1<1||Day1>DaysInMonth[Visokos][Month1- 1])); do { printf("Введите день 2 (1-31) : "); scanf("%d",&Day2); printf("Введите месяц 2 (1-12) : "); scanf("%d",&Month2); } while ((Month2<1||Month2>12)||(Day2<1||Day2>DaysInMonth[Visokos][Month2- 1])); if(Month1>Month2) { //вторая дата должна быть старше первой Temp=Month1;Month1=Month2;Month2=Temp; //меняем даты местами Temp=Day1;Day1=Day2;Day2=Temp; } 180 Diff=0; //итоговая разность в днях if (Month1==Month2) Diff=abs(Day1-Day2); //если один и тот же месяц то просто вычитаем дни else { for (i=Month1;i месяцам Diff += DaysInMonth[Visokos][i]; // и сложить дни Diff+=(DaysInMonth[Visokos][Month1-1]-Day1);//добавить отстатки дней от первого месяца Diff+=Day2; //и еще добавить дни второго месяца } //вывести результат printf ("Между %d.%d.%d и %d.%d.%d",Day1,Month1,CurrentYear,Day2,Month2, CurrentYear); printf ("\nРазница = %d дней\n",Diff); getch(); } Результат выполнения программы Введите год : 2008 Введенный год 2008. Високосный год! Введите день 1 (1-31):3 Введите месяц 1 (1-12) :10 Введите день 2 (1-31) : 12 Введите месяц 2 (1-12) : 10 Между 3.10.2008 и 12.10.2008 Разница = 9 дней Пример 6. Алгоритм построения треугольника Паскаля Треугольник Паскаля − арифметический треугольник, образованный биномиальными коэффициентами. Назван в честь Блеза Паскаля. Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси. #include #include #include #include #define M 13 int main() { int n; int a[M][M]; int i, j, k; 181 do { printf ("Введите n < 12 : "); scanf("%d", &n); } while (n >= 12); puts ("Таблица 1"); for (i = 0; i <= n; i++) { for (j = 0; j <= i; j++) { if ((i == j) || (j == 0)) a[i][j] = 1; else a[i][j] = a[i-1][j-1] + a[i-1][j]; printf ("%4d", a[i][j]); } printf ("\n"); } Puts ("Таблица 2"); for (i = 0; i <= n; i++) { for (j = 0;j <= i; j++) { if (j == 0) for (k = 0; k < (n-i); k++) printf (" "); printf ("%6d", a[i][j]); } printf ("\n"); } getch (); } Результат выполнения программы Введите n < 12 : 7 Таблица 1 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 Таблица 2 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 182 Пример 7. Сравнение способов сортировки: способ «пузырька», сортировка выбором и метод простых вставок. #include #include #include #include #include inline void Change(int a[], int first, int second) // меняем местами элементы буфера first на second // a[] - заданный массив // first и second - номера элементов массива a, которые надо поменять местами! { if (first == second) // Если одинаковые номера элементов, то не нужно менять их местами return; int i; i = a[second]; a[second] = a[first]; a[first] = i; } int FindMax(int a[], int max) // Поиск максимального числа в массиве от a[0] до a[max] // a[] - заданный массив // max - размер массива a { int imax = 0; for (int i = 0; i <= max; i++) { if (a[imax] < a[i]) imax = i; } return imax; } void SelectSort(int b[], int max) // Сортировка выбором // b[] - заданный массив // max - размер массива b { int i1; for (int i = max - 1; i > 0; i--) { i1 = FindMax(b, i); // Находим самое максимальное число в промежутке от a[0] до a[i] Change(b, i, i1); // ставим максимальное число в конец (а именно на место эллемента под номером i) } } void BubbleSort(int c[], int max) // Сортировка "пузырьком" // c[] - заданный массив // max - размер массива c { for (int i1 = 0; i1 < max; i1++) { for (int i = max-2; i >= i1; i--) 183 { if (c[i+1] > c[i]) continue; Change(c, i, i+1); // Двигаем минимальное число вверх, тем самым сортируя числа } } } void InsertSort(int d[], int max) // Сортировка методом простых вставок // d[] - заданный массив // max - размер массива c { int temp, j; for (int i = 1; i < max; i++) // цикл проходов, i - номер прохода { temp = d[i]; j = i - 1; // поиск места элемента в готовой последовательности while (j >= 0 && d[j] > temp) { d[j+1] = d[j]; // сдвигаем элемент направо, пока не дошли --j; } // место найдено, вставить элемент d[j+1] = temp; } } int main() { int MAX; printf("Введите количество элементов : "); scanf("%i", &MAX); // Объявляем буферы int *a = new int[MAX]; int *b = new int[MAX]; int *c = new int[MAX]; int *d = new int[MAX]; srand((unsigned)time(0)); for (int i = 0; i < MAX; i++) { a[i] = rand(); // заполняем случайными числами b[i] = a[i]; // делаем копию c[i] = a[i]; // делаем копию d[i] = a[i]; // делаем копию } clock_t begin, end; begin = clock(); BubbleSort(b, MAX); // Сортируем массив с методом "пузырька" end = clock(); float f0 = (float)(end-begin); // Измеряем время, занятое сортировкой методом "пузырька" printf ("\nСортировка массива из %i элементов методом "пузырька" заняла \t %.0f msec.\r\n", MAX, f0); begin = clock(); SelectSort(c, MAX); // Сортируем массив b методом выбора end = clock(); 184 float f1 = (float)(end-begin); // Измеряем время, занятое сортировкой методом выбора printf ("Сортировка массива из %i элементов методом выбора заняла \t%.0f msec.\r\n", MAX, f1); begin = clock(); InsertSort(d, MAX); // Сортируем массив b методом вставок end = clock(); float f2 = (float)(end-begin); // Измеряем время, занятое сортировкой методом вставок printf ("Сортировка массива из %i элементов методом вставок заняла \t%.0f msec.\r\n", MAX, f2); // Просмотр отсортированных данных? printf("\r\n\r\n\r\nВы хотите просмотреть отсортированные данные? (y/n)"); short Key = 0; while (Key = _getch()) // Ожидание нажатия на кнопку { if (Key == 'n' || Key == 'N' || Key == 27) // если нажата кнопк N или Esc, то return 0; // выход else if (Key == 'y' || Key == 'Y') // если y, то break; // то продолжаем } printf("\r\n\r\n\r\n\r\n"); printf(" N.\tБез сортировки\tN.\tМетод «пузырька»\tN.\tМетод выбора\tN.\tМетод вставки\r\n"); printf("\r\n"); for (int i = 0; i < MAX; i++) printf("%3i.\t%5i\t%3i.\t%5i\t%3i.\t%5i\t%3i.\t%5i\r\n", i+1, a[i], i+1, b[i], i+1, c[i], i+1, d[i]); // Печать содержимого массивов printf("\r\nНажмите любую кнопку для продолжения\r\n"); Key = 0; while (!Key) Key = _getch(); // Ожидание нажатия на кнопку } Результат выполнения программы Введите количество элементов : 10000 Сортировка массива из 10000 элементов методом "пузырька" заняла 1139 msec. Сортировка массива из 10000 элементов методом выбора заняла 175 msec. Сортировка массива из 10000 элементов методом вставок заняла 113 msec. Вы хотите просмотреть отсортированные данные? (y/n) N. Без сортировки N. Метод «пузырька» N. Метод выбора N. Метод вставки 1. 30410 1. 1072 1. 1072 1. 1072 2. 7475 2. 1219 2. 1219 2. 1219 3. 13312 3. 1405 3. 1405 3. 1405 4. 30386 4. 1911 4. 1911 4. 1911 5. 27070 5. 3080 5. 3080 5. 3080 6. 11743 6. 6686 6. 6686 6. 6686 185 7. 23967 7. 6981 7. 6981 7. 6981 8. 7718 8. 7229 8. 7229 8. 7229 9. 24750 9. 7457 9. 7457 9. 7457 10. 29293 10. 7475 10. 7475 10. 7475 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Пример 8. Процедуры для организации и работы с односвязными списками. #include #include #include #include #include #include using namespace std; class Node { public: int number; Node* next; }; int main() { Node* head = NULL; Node* lastPtr = NULL; short action = -1; while (1) { printf("1. Добавить Элемент\n"); printf("2. Просмотр Списка\n"); printf("3. Поиск Элемента\n"); printf("4. Удалить Элемент\n"); printf("5. Удалить Элемент По Выбору\n"); printf("0. Выход\n\n"); printf("Ваш Выбор: "); cin>>action; if (action == 0) { system("CLS"); break; } if (action == 1) { system("CLS"); Node* ptr = new Node; int numb = -1; printf("Введите Число: "); cin>>numb; ptr->number = numb; ptr->next = NULL; if (head == 0) { head = ptr; lastPtr = ptr; system("CLS"); continue; 186 } lastPtr->next = ptr; lastPtr = ptr; system("CLS"); continue; } if (action == 2) { Node* ptr = NULL; system("CLS"); if (head == NULL) { printf("\t!!! СПИСОК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("* * * * * СПИСОК * * * * *\n\n"); ptr = head; while (1) { cout< number<<" "; if (ptr->next == 0) break; ptr = ptr->next; } cout<<"\n\n"; system("PAUSE"); system("CLS"); continue; } if (action == 3) { Node* ptr = NULL; int key = -1; system("CLS"); if (head == NULL) { printf("\t!!! СПИСОК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("Введите Элемент Для Поиска: "); cin>>key; ptr = head; while (1) { if (key == ptr->number) { printf("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n"); break; } if (ptr->next == NULL) { printf("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n"); break; } ptr = ptr->next; } system("PAUSE"); system("CLS"); 187 continue; } if (action == 4) { system("CLS"); Node* ptrDelete = NULL; if (head == NULL) { printf("\t!!! СПИСОК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } if (head->next == NULL) { head = NULL; delete head; continue; } ptrDelete = head; head = ptrDelete->next; delete ptrDelete; continue; } if (action == 5) { system("CLS"); Node* ptrPrev = NULL; Node* ptrDelete = NULL; int key = -1; if (head == NULL) { printf("\t!!! СПИСОК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("Введите Элемент Для Удаления: "); cin>>key; ptrDelete = head; if (ptrDelete->number == key) { head = ptrDelete->next; delete ptrDelete; system("CLS"); continue; } while (1) { if (key == ptrDelete->number) { ptrPrev->next = ptrDelete->next; delete ptrDelete; break; } if (ptrDelete->next == 0) { printf("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n"); system("PAUSE"); break; } ptrPrev = ptrDelete; 188 ptrDelete = ptrDelete->next; } system("CLS"); continue; } if (action > 5) { system("CLS"); printf("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n"); system("PAUSE"); system("CLS"); continue; } } } Результат выполнения программы (меню программы) 1. Добавить Элемент 2. Просмотр Списка 3. Поиск Элемента 4. Удалить Элемент 5. Удалить Элемент По Выбору 0. Выход Ваш Выбор: Пример 9. Процедуры для организации и работы с двусвязными списками. #include #include #include #include #include |