Помогите решить задачу на С+

Статус: Offline
Реєстрація: 26.09.2008
Повідом.: 101
Помогите решить задачу на С++

В одномерном массиве найти наибольшую по длине повторяющуюся последовательность символов. Заранее благодарен
 
В одномерном массиве найти наибольшую по длине повторяющуюся последовательность символов. Заранее благодарен

А не могли бы Вы уточнить задание, что означает эта самая "повторяющаяся последовательность"? Последовательность из одинаковых символов типа "aaa"? Или последовательность, встречающаяся в строке более одного раза типа "ab" в "abcab"? Или что-то ещё другое?
Cложность задачи от этого сильно меняется. И если вариант таки №2, то насколько большой объём данных и насколько быстро оно должно работать? Т.е. нужно ли реализовывать префиксное дерево (см https://en.wikipedia.org/wiki/Trie) или полный перебор прокатит?
 
Уточнение

Суть состоит в том чтобы можно было ввести к примеру "asddspppar" и нужно чтобы программа выбрала "ppp". Объем данных очень маленький.
 
То есть: в одномерном массиве найти наибольшую по длине непрерывную последовательность одинаковых символов. ТС, так будет звучать постановка задачи?
 
Это очень сложная задача:) Даже останаиваться не хочу. Интересней таки было б выделить повторяющиеся последовательности:) Разбор по дереву, это слишком сурово. И кроме того прийдется запускать новое дерево, как только обнаружится буква уже участвующая в ветке для анализа на повторение последовательности. Можно проще. Пройтись в цикле по массиву с целью поиска повторяющихся символов и составить массивы из их позиций по возрастанию. Которые потом и проанализировать. В анализе будут исключены не повторяющиеся символы, и не рядом стоящие. Вообщем будет над чем подумать для повышения эффективности.
Это так общие рассуждения..
 
Очень легкая задача!
 
Вам дешевле будет дать денег преподу, чем нанять тут человека который решит вам это "сложную" задачу. Если есть желание, пишите в личку, где-то за каких то 50 грн. я думаю сделаю.
 
На вскидку тут 15-20 строчек кода от силы ))) Другое дело что ...

+1

Это юмор или таки понял? Я ж не про поиск последовательности одинаковых букв. Могу сказать что меня редко понимают.. А писать подробно дурной тон..
 
Попробуем вот так вот на C
Код:
struct Sequence
{
	char c;
	int pos;
	int length;
};

Sequence findMax(char str[])
{
	Sequence max;
	max.c = 0;
	max.length = 0;
	max.pos = -1;

	Sequence cur;
	cur.pos = 0;
	cur.length = 0;
	cur.c = 0;

	for(const char* p = str; *p; p++)
	{
		if(*p != cur.c)
		{
			if(cur.length > max.length)
			{
				max = cur;
			}
			cur.pos += cur.length;
			cur.length = 0;
			cur.c = *p;
		}
		cur.length++;
	}
	return max;
}
Пример использования:
Код:
int main(int argc, char* argv[])
{
	char str[] = "asddspppar";
	
	Sequence max = findMax(str);

	printf("%s\nchar=%c\tpos=%d\tlength=%d\n", str, max.c, max.pos, max.length);

	return 0;
}
При желании можно переделать на строки из std, но лень.
 
Это юмор или таки понял? Я ж не про поиск последовательности одинаковых букв. Могу сказать что меня редко понимают.. А писать подробно дурной тон..

Написать можно разными способами, однако чтобы написать самый короткий и быстродействующий способ необходимо подумать. Я правильно вас понял? :)
 
Насчет быстродействия. Думаю, что пример от уважаемого balkauser можно оптимизировать. :)
 
Не буду создавать новую тему, прошу совета в решении задачи сортировки.
есть к примеру массив

int A[7] = {5, 15, 10, 16, 0, 0, 10};

необходимо его отсортировать по возрастанию, но чтоб нули были в конце, т.е.

5,6,10,10,16,0,0

Как задать правильно условие для нулей?
 
эм... проверяйте, если у вас значение 0 то замените его на 2147483648, после чего пройдитесь в конце по массиву и присвойте значениям 2147483648 значение 0. вариант калечный, но вероятность того, что в вашем массиве будет столь большое число практически нулевая
зы: еще считайте количество нулей в массиве, и заменяйте число 2147483648 на 0 с конца массива, тогда вариант да же будет правильно работать при условии что у вас в массиве да же будут числа равные 2147483648.
 
Останнє редагування:
Эх, сессия пришла, и ничего умнее чем написать на ХФ в голову не пришло...
 
5 коп критики, если не возражаете ...

эм... проверяйте, если у вас значение 0 то замените его на 2147483648,

ОС в задании не оговорена ...
я к тому, что integer не всегда был 4-х байтным ...
и не обязательно будет таковым в дальнейшем ...

после чего пройдитесь в конце по массиву и присвойте значениям 2147483648 значение 0. вариант калечный, но вероятность того, что в вашем массиве будет столь большое число практически нулевая

это теоретическая задача ... посему вероятность встречи такого числа равна вероятности встречи любого числа из диапазона int ...
 
5 коп критики, если не возражаете ...



ОС в задании не оговорена ...
я к тому, что integer не всегда был 4-х байтным ...
и не обязательно будет таковым в дальнейшем ...



это теоретическая задача ... посему вероятность встречи такого числа равна вероятности встречи любого числа из диапазона int ...

критика принята, тогда оправдаюсь так: заменить 0 на максимальное число которое может содержать в себе массив - это "раз". а по поводу теоретической задачи я уже писал, что если посчитать количество нулей при замене и с конца отсортированного массива заменить количество максимальных значений на нули то задача будет решена правильно

добавлю немного кода: (прошу прощение за мой С++, давно не писал)
Код:
const int max_val = 7;
int mas[] = {1,2,3,0,5,2147483648,0}; //при условии что int - 4-х байтное число
int counter = 0;
for(int i=0;i<max_val;i++)
{
     if(mas[i] == 0)
    {
         counter++;
         mas[i] = 2147483648;
    }
}
SortMass(mas);
for(int i = max_val-1;i>=max_val - (counter +1); i--) //по поводу i>=max_val - (counter +1) не уверен.
{
   mas[i] = 0;
}

в общем как нить так.
 
Останнє редагування:
Не буду создавать новую тему, прошу совета в решении задачи сортировки.
есть к примеру массив

int A[7] = {5, 15, 10, 16, 0, 0, 10};

необходимо его отсортировать по возрастанию, но чтоб нули были в конце, т.е.

5,6,10,10,16,0,0

Как задать правильно условие для нулей?

Я предпочитаю размещать логику сравнения там, где её и положено быть - в компараторе (методе или объекте, смотря по языку/библиотеке). Поэтому предлагаю такое решение с помощью стандартной qsort (
Тільки зареєстровані користувачі бачать весь контент у цьому розділі
):
Код:
int compare( const void *arg1, const void *arg2 )
{
	int a = *((const int*)arg1);
	int b = *((const int*)arg2);
	if(a == b) return 0;
	if(a == 0) return 1;
	if(b == 0) return -1;
	return (a > b) ? 1 : -1;
}


int main(int argc, char* argv[])
{
	int A[] = {5, 15, 10, 16, 0, 0, 10};
	const int count = sizeof(A) / sizeof(int);
	qsort( (void *)A, count, sizeof(int), compare );

	return 0;
}
Ввод-вывод, надеюсь, сможете сделать сами (не забыв правильно определить count)
 
Назад
Зверху Знизу