Методичка по С. Методические указания к лабораторному практикуму по дисциплине Программирование на языках высокого уровня (язык Си) москва 2005
 Скачать 429.5 Kb.
|
Примеры решения задачЗадача 6.1. Подсчитать число размещений A(k, r) по формуле A(k, r) = k! / (k - r)! при k r, где n! = 1 при n= 0, n! = (n-1)! nпри n1. #include int fakt(int n) {if (n==0) return 1; return fakt(n-1)*n; } void main() {int k,r; do printf("введите k,r (k>=r)\n"); while ((scanf("%d%d",&k,&r))!=2||k<r); //scanf возвращает число успешно прочитанных аргументов printf("a=%d",(int)fakt(k)/fakt(k-r));//результат приведен к типу int } Задача 6.2. Найти в бинарном дереве число, наиболее удаленное от среднего арифметического минимума и максимума. #include #include #include #include #include #define NODE struct node NODE {int info; NODE *left,*right;}; NODE *newn(int x) //создание нового узла, с числом x в поле данных {NODE *uk; uk=(NODE*) malloc(sizeof(NODE));//выделение памяти uk->info=x;//запись числа в поле данных uk->left=uk->right=NULL;//указатели на левого и правого сына = NULL return(uk); } void setleft(NODE*p, int x)//присоединение числа x к узлу p слева {p->left=newn(x);} void setright(NODE*p, int x) //присоединение числа x к узлу p справа {p->right=newn(x);} NODE *form()//формирование дерева { int n; NODE *der=NULL,*next,*tek;//указ. на корень, текущий и следующий puts("введите данные//конец ввода - буква"); if(scanf("%d",&n)==1)//если данные успешно считаны { der=newn(n);//формирование корня while(scanf("%d",&n)==1)//пока есть данные { next=tek=der; while (next!=NULL)//поиск узла, к которому подключаем n { tek=next; if (n else next=tek->right; } if(n<tek->info) setleft(tek,n);//присоединение слева или справа else setright(tek,n); } }return der; } //вывод дерева на экран в виде дерева при прямом обходе void printder(NODE *der,int x, int y, int d) { if (! der ) return; gotoxy(x,y);//курсор помещается на знакоместо с коорд. (x,y) printf("%d",der->info);//печать числа if (der->left)//обход левого поддерева (если оно не пустое) printder(der->left,x-d,y+2,d/2); if (der->right)//обход правого поддерева (если оно не пустое) printder(der->right,x+d,y+2,d/2); } //глобальные переменные int max,min;//максимальное и минимальное число в дереве float srar,rmax=-1e38;//среднее арифметическое чисел дерева // и максимальное расстояние от числа до среднего int numb;//искомое число //поиск max для прямого обхода дерева void searchmax(NODE *der) {if(der==NULL) return; if(der->info>max) max=der->info; searchmax(der->left);//можно опустить searchmax(der->right); } //поиск числа, наиболее удаленного от среднего арифметического //min и max при прямом обходе дерева void search(NODE *der) {if(der==NULL) return;//тривиальный случай if(fabs((der->info)-srar)>rmax) rmax=fabs((der->info)-srar), numb=der->info; search(der->left); search(der->right); } void main() { NODE *der,*tek; clrscr(); puts("Создание дерева\n"); der=form(); if (!der) puts("дерево пустое"); else {printder(der,40,4,20); max=-32768; searchmax(der);//поиск max с использованием рекурсии printf("\nmax %d",max); min=der->info;//поиск min без использования рекурсии при условии //того, что дерево сформировано так, что числа, меньшие корня, //размещаютя в левом поддереве, а остальные – в правом while (tek->left) tek=tek->left, min=der->info; printf("\nmin %d",min); srar=(min+max)/2; search(der); printf("\nnumb %d",numb); }getch(); } Пример использования рекурсии для проверки правильности записи арифметического выраженияПусть задан синтаксис арифметического выражения:  Необходимо проверить правильность записи арифметического выражения в соответствии с заданным синтаксисом. Структура данных: char ae[80], //арифметическое выражение * pf ; // указатель на текущую позицию в ae ЗАМЕЧАНИЯ: Каждая функция получает указатель на текущую позицию в ae и пытается выделить соответствующий элемент, начиная с этой позиции. После выделения элемента указатель перемещается на следующую позицию после этого элемента. Каждая функция возвращает значение 0, если элемент выделен, в противном случае возвращается 1. Каждая функция использует только глобальные переменные, чтобы их значения не копировались при каждом вызове функций. #include #include #include #define ZNAK *pf == '+' || *pf == '-' //макроопределение //глобальные переменные char ae[80], *pf; //прототипы функций int fae (); int fslag (); int fmnog (); int fper (); int fid(); int fconst(); void main () { printf ("Введите выражение: \n"); gets (ae); pf=ae; printf ("выражение: \n %s \n",pf); if (fae () || *pf ) /* то есть в выражении есть ошибка, или после нуль-символа есть еще символы, т.е. pf != ‘\0’ (после fae указатель pf должен показывать на конец выражения:‘\0’)*/ printf (" ошибка - %d символ %c \n", pf-ae,*pf); /* разность указателей pf-ae равна количеству символов, то есть номеру символа. Указатель на char *pf даст символ, то есть содержимое по адресу */ else printf (" выражение правильно \n"); getch(); } int fae ()//проверка правильности арифметического выражения { if (ZNAK) pf++;//по синтаксису - пропуск возможного знака while (1) // бесконечный цикл { if (fslag()) return (1);// есть ошибка в слагаемом if (ZNAK) pf++;// пропуск знака в арифм. выражении else return (0);// конец арифметического выражения } } int fslag ()//проверка правильности слагаемого { while (1) { if (fmnog()) return (1);//в множителе есть ошибка if (*pf == '*' || *pf =='/') pf++; else return (0);// конец арифметического выражения } } int fmnog ()//проверка правильности множителя { if (*pf =='(') //выражение в скобках { pf++; //рекурсия if (fae()) return (1); //есть ошибка в ae if (*pf != ')' ) return(1);//после ae не скобка else pf++; // пропуск закрывающейся скобки } else if (fper() && fconst()) return(1); //если дальше в выражении не переменная и не константа return (0); } int fper ()//проверка правильности переменной { if (fid()) return(1); // есть ошибка в идентификаторе if (*pf =='[') { do { pf++; if (fae()) return (1); //есть ошибка в ae } // пока запятая, проверяется fae в цикле while (*pf ==','); if (*pf != ']' ) return(1); pf++; } return (0); } int fid()//проверка правильности идентификатора { if (isalpha(*pf)==0) return(1);//первый символ - не буква while (isalpha(*pf) || isdigit(*pf)) pf++; //пропуск букв и цифр return(0); // в идентификаторе может быть одна буква } int fconst() //проверка правильности константы без знака { int flag =1; //флаг определяет наличие цифр в мантиссе while (isdigit(*pf)) //пока есть цифры { flag=0; pf++; // пропуск цифр в мантиссе } if (*pf =='.') { pf++; while(isdigit(*pf)) {pf++; flag=0; } //если есть цифры, после цикла flag = 0,иначе flag =-1 } if (flag) return(1); // если нет цифр if (*pf =='E') // проверка наличия экспоненты { pf++; if(ZNAK) pf++;//пропуск возможного знака if(!isdigit(*pf)) return(1); // в порядке должна быть хотя бы одна цифра while (isdigit(*pf)) pf++;//пропуск цифр } return(0); } Библиографический списокБ. Керниган, Д. Ритчи, А. Фьюэр. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 1985. М. Уэйт. С. Прата, Д. Мартин. Язык Си. М.: Мир, 1988. В.Г. Ссорин. Методические указания по выполнению лабораторных работ по курсу "Программное обеспечение ЭВМ" М.: МИЭМ, 1991. Руководство пользователя TURBO-C. Borland, 1989. Фигурнов В.Э. "IBM PC для пользователя". изд. 2-е, перераб. и доп. М.: Финансы и статистика, Компьютер-пресс, 1991. Учебное издание Составители: ЕРОХИНА Елена Альфредовна ЗАЙЦЕВА Лариса Викторовна ССОРИН Владимир Гелиосович Редактор С.П. Клышинская Технический редактор О.Г. Завьялова http://www.miem.edu.ru/rio/ rio@miem.edu.ru Подписано в печать __.__.05. Формат 60х84/16. Бумага типографская № 2. Печать - ризография. Усл. печ. л. 2,25 Уч.-изд. л. 2,03 Тираж 50 экз. Заказ . Бесплатно Изд. № . Московский государственный институт электроники и математики 109028 Москва, Б. Трехсвятительский пер., 3/12. Отдел оперативной полиграфии Московского государственного института электроники и математики. 113054 Москва, ул. М. Пионерская, 12. |