Читайте также:
|
Дан массив строк. Вывести на экран все слова, являющиеся анаграммами.
Анаграммами называются слова, состоящие из одинаковых букв, отличающихся лишь порядком их следования. Например: автор – товар – отвар – тавро – …; апельсин – спаниель.
Для поиска анаграмм нужно произвести следующие действия:
отсортировать буквы всех слов по алфавиту;
реализовать функцию сравнения строк;
отсортировать слова с сортированными буквами по алфавиту. Для этого нужно создать массив индексов и при сортировке переставлять элементы в массиве индексов, не изменяя массив слов;
просмотреть массив строк в порядке, указанном в массиве индексов, повторяющиеся слова напечатать в первоначальном виде. Слова-анаграммы печатаются в строчку (таких слов может быть два и более).
Закодируем варианты сортировки следующим образом: по убыванию (код 0х) – по возрастанию (код 1х); с начала (во внутреннем цикле данные просматриваются с начала, используются операции типа i++, код х0) – с конца (во внутреннем цикле данные просматриваются с конца, используются операции типа i--, код х1).
Номер варианта задания равен остатку от деления номера студента по журналу на 16. Этот остаток кодируется четырьмя битами. Старшие два бита означают тип сортировки букв в слове, два младших означают тип сортировки индексов. Например, вариант 0110 (6) означает, что буквы нужно сортировать по убыванию, начиная с конца, а массив индексов нужно сортировать по возрастанию, начиная с начала.
В простейшем варианте можно реализовать сортировку пузырьком (поэлементную). Студенты, претендующие на повышенную оценку автоматом, должны реализовать быструю сортировку.
Содержание отчета
Отчет должен содержать листинг программы, в которой реализованы задание и функции тестирования, представлены результаты работы программы.
Контрольные вопросы
1) Опишите простой алгоритм сортировки.
2) Опишите алгоритм быстрой сортировки.
3) Как изменятся условия для простого алгоритма сортировки, если элементы массива нужно расположить в порядке убывания?
4) Как изменятся условия для простого алгоритма сортировки, если элементы в массиве начать располагать начиная с наибольшего?
5) Объясните назначение функции print_mas из примера в теоретической части.
6) Какое количество операций сравнения потребуется для простого алгоритма сортировки при количестве элементов, равном шести?
7) Как связаны между собой значения, обозначенные одинаковыми буквами со штрихом и без штриха?
ПРИЛОЖЕНИЕ
ПРИМЕР ТЕСТИРОВАНИЯ ФУНКЦИЙ
// Пример тестирования функций
// Для вывода отладочных сообщений нужно определить символ DEBUG_MAX
// Сделать это можно при компиляции с помощью ключа –D:
// Например: «C:\MinGW\bin>gcc d:/work/prog4_1.c -D DEBUG_MAX»
#include "stdio.h"
int max_len_equ_symb(char* str, int n)
// Функция находит количество элементов в наиболее длинной последовательности элементов в массиве str
// n - количество элементов в массиве str
{
int i; // Текущий просматриваемый символ
int l=1; // Максимальное количество одинаковых символов среди просмотренных
int m=1; // Текущее количество символов
char c=str[0]; // Последний встретившийся символ
for(i=1; i<n; i=i+1)
{
if(str[i]==c)
m=m+1;
else
{
m=1;
c=str[i];
}
if(m>l)
l=m;
// Это директивы препроцессора
// Все, что между ними, будет включено в программу только в случае, если определен символ DEBUG_MAX
#ifdef DEBUG_MAX
О к о н ч а н и е п р и л.
printf("i = %i, l= %i \n", i, l); // Это отладочные сообщения, которые будут печататься только при отладке. Выводим на экран интересующие нас переменные
#endif
}
return l;
}
// В примере тесты проводятся в главной функции программы
// В общем случае нужно создавать тестирующие функции для каждой созданной функции
int main()
{
int l, n=10;
// Строки, на которых мы будем тестировать нашу функцию:
char str1[]="aaabbbccdd\0";
char str2[]="abbbbbccdd\0";
char str3[]="aabbbcdddd\0";
l = max_len_equ_symb(str1, n);
printf("\nTEST 1\n str=%s,\n l=%i\n", str1,l);
// Для первой строки функция должна выдать результат 3
if (l==3)
printf("Test passed\n\n");
else
printf("Test fail\n\n");
l = max_len_equ_symb(str2, n);
printf("\nTEST 1\n str=%s,\n l=%i\n", str2,l);
if (l==5)
printf("Test passed\n\n");
else
printf("Test fail\n\n");
l = max_len_equ_symb(str3, n);
printf("\nTEST 1\n str=%s,\n l=%i\n", str3,l);
if (l==4) printf("Test passed\n\n");
else
printf("Test fail\n\n");}
* * *
Дата добавления: 2015-01-07; просмотров: 51 | Поможем написать вашу работу | Нарушение авторских прав |