Разработка программного обеспечения. Функция, оставляющую в строке по одному пробелу между словами, страница 9

 

Описание алгоритма: В функцию передается переменная и указатель на результирующий массив. Изначально проверяются условия, если заданное число =2, то 2 записывается в массив простых чисел и программа завершается. если заданное число меньше 2, то выдается сообщение об ошибки и программа завершается. Во всех остальных случаях, в массив простых чисел заноситься первое простое число 2,  и Дале организуется цикл, от 3 до заданного числа. Если число из этого диапазона нацело делиться на число из массива простых чисел, оно просто пропускается, если же при делении получается остаток, это значит, что число является простым и оно помешается в массив простых чисел. Таким образом, проверяются все числа из диапазона от 3 до заданного числа и заполняется массив простых чисел.

/* в функцию передается переменная (num) и указатель на начало результирующего массива (*mas)*/

int func(int num, int *mas){

int len = 2;  int i, j,index = 0, flag;

if (num == 2) {mas[0] = 2;return 1;}  //если заданное число равно 2, то оно записывается в массив и программа завершается

if (num < 2){ printf(“ERROR \n”); return 0;}         //если число меньше двух, то программа завершается c сообщением об ошибке

mas[index ++] = 2;                          //записываем в массив первое простое число =2

for (i = 3;i < num;i ++){                 //организуем цикл от 3 до заданного числа

flag = 1;

for (j = 0;j < len - 1;j ++){    //цикл, по всем элементам массива

if ((i % mas[j]) == 0) flag = 0;  //если число (от 3 до заданного) делится на элементы массива на цело

//устанавливаем flag = 0

}

if (flag == 1) {                                  //если число (от 3 до заданного) является простым и его нет в массиве

mas = realloc(mas, len * sizeof(int)); //выделяем память под новый элемент в массиве простых чисел

len ++;                                                //увеличиваем размер массива на 1

mas[index ++] = i;        //и записываем туда это число

}    }      

return len;   }

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

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

Предполагаем что все строки в массиве правильные.

Алгоритм двоичного поиска заключается: разбиваем основной  диапазон на 2 под диапазона  и  определяем в какой из них попадает искомый элемент, выбираем его за основной и.т.д. пока не найдется искомый элемент…

Описание алгоритма: В функцию передается указатель на массив, кол-во элементов в массиве и указатель на строку поиска.

Устанавливаем первоначальные границы min=0 max=кол-воэлементов в исходном массиве, разбиваем его на два, определяем в какой диапазон входит искомая строка, выбираеи

void *binary_search(char **strs,int count, char *pattern){

    int i,low,high,mid=0;

    low=0; high = count-1;       //задаём начальный диапазон

        while(low<=high)      

        {

            mid = (high+low)/2;    //определяем середину диапазона

            if(strlen(strs[mid]<strlen(search))continue     //смотрим что длина строки в

                                              // массиве не меньше длинны искомой строки

            if(memcmp(strs[mid],pattern,(strlen(pattern)-1)) > 0) high = mid-1;       // если выполняется условие, искомая строка входит в верхний под диапазон

            else if(memcmp(strs[mid],pattern,(strlen(pattern)-1)) < 0) low = mid+1; // если выполняется условие, искомая строка входит в нижний под диапазон

            else return strs[mid]; //возвращаем позицию найденной строки

        }

return -1; // возвращаем -1 если строка не найдена

}

memcmp(strs[mid],pattern,(strlen(pattern)-1)) > 0