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

Sasha9132 · 09.12.2009

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

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

balkauser · 10.12.2009

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

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

Sasha9132 · 10.12.2009

Уточнение

Суть состоит в том чтобы можно было ввести к примеру "asddspppar" и нужно чтобы программа выбрала "ppp". Объем данных очень маленький.

ASokol · 10.12.2009

То есть: в одномерном массиве найти наибольшую по длине непрерывную последовательность одинаковых символов. ТС, так будет звучать постановка задачи?

Sasha9132 · 10.12.2009

ASokol сказав(ла):
То есть: в одномерном массиве найти наибольшую по длине непрерывную последовательность одинаковых символов. ТС, так будет звучать постановка задачи?

именно так

batu · 10.12.2009

Это очень сложная задача

Даже останаиваться не хочу. Интересней таки было б выделить повторяющиеся последовательности

Разбор по дереву, это слишком сурово. И кроме того прийдется запускать новое дерево, как только обнаружится буква уже участвующая в ветке для анализа на повторение последовательности. Можно проще. Пройтись в цикле по массиву с целью поиска повторяющихся символов и составить массивы из их позиций по возрастанию. Которые потом и проанализировать. В анализе будут исключены не повторяющиеся символы, и не рядом стоящие. Вообщем будет над чем подумать для повышения эффективности.
Это так общие рассуждения..

Kvest · 10.12.2009

Очень легкая задача!

Lam · 10.12.2009

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

Kvest · 10.12.2009

На вскидку тут 15-20 строчек кода от силы ))) Другое дело что ...

batu сказав(ла):
будет над чем подумать для повышения эффективности.

+1

batu · 10.12.2009

Kvest сказав(ла):
На вскидку тут 15-20 строчек кода от силы ))) Другое дело что ...

+1

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

balkauser · 10.12.2009

Попробуем вот так вот на 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, но лень.

Kvest · 10.12.2009

batu сказав(ла):
Это юмор или таки понял? Я ж не про поиск последовательности одинаковых букв. Могу сказать что меня редко понимают.. А писать подробно дурной тон..

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

Sasha9132 · 10.12.2009

Вери спс.

ASokol · 10.12.2009

Насчет быстродействия. Думаю, что пример от уважаемого balkauser можно оптимизировать.

fuel · 10.12.2009

Не буду создавать новую тему, прошу совета в решении задачи сортировки.
есть к примеру массив

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

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

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

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

Lam · 10.12.2009

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

FreakOnALeash · 10.12.2009

Эх, сессия пришла, и ничего умнее чем написать на ХФ в голову не пришло...

fatalex · 10.12.2009

5 коп критики, если не возражаете ...

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

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

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

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

Lam · 10.12.2009

fatalex сказав(ла):
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;
}

в общем как нить так.

balkauser · 10.12.2009

fuel сказав(ла):
Не буду создавать новую тему, прошу совета в решении задачи сортировки.
есть к примеру массив

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)