Допомагаємо ЗСУ!

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

🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
Статус: Offline
Реєстрація: 26.09.2008
Повідом.: 101
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #1
Помогите решить задачу на С++

В одномерном массиве найти наибольшую по длине повторяющуюся последовательность символов. Заранее благодарен
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #2
В одномерном массиве найти наибольшую по длине повторяющуюся последовательность символов. Заранее благодарен

А не могли бы Вы уточнить задание, что означает эта самая "повторяющаяся последовательность"? Последовательность из одинаковых символов типа "aaa"? Или последовательность, встречающаяся в строке более одного раза типа "ab" в "abcab"? Или что-то ещё другое?
Cложность задачи от этого сильно меняется. И если вариант таки №2, то насколько большой объём данных и насколько быстро оно должно работать? Т.е. нужно ли реализовывать префиксное дерево (см https://en.wikipedia.org/wiki/Trie) или полный перебор прокатит?
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #3
Уточнение

Суть состоит в том чтобы можно было ввести к примеру "asddspppar" и нужно чтобы программа выбрала "ppp". Объем данных очень маленький.
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #4
То есть: в одномерном массиве найти наибольшую по длине непрерывную последовательность одинаковых символов. ТС, так будет звучать постановка задачи?
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #5
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #6
Это очень сложная задача:) Даже останаиваться не хочу. Интересней таки было б выделить повторяющиеся последовательности:) Разбор по дереву, это слишком сурово. И кроме того прийдется запускать новое дерево, как только обнаружится буква уже участвующая в ветке для анализа на повторение последовательности. Можно проще. Пройтись в цикле по массиву с целью поиска повторяющихся символов и составить массивы из их позиций по возрастанию. Которые потом и проанализировать. В анализе будут исключены не повторяющиеся символы, и не рядом стоящие. Вообщем будет над чем подумать для повышения эффективности.
Это так общие рассуждения..
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #7
Очень легкая задача!
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #8
Вам дешевле будет дать денег преподу, чем нанять тут человека который решит вам это "сложную" задачу. Если есть желание, пишите в личку, где-то за каких то 50 грн. я думаю сделаю.
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #9
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #10
На вскидку тут 15-20 строчек кода от силы ))) Другое дело что ...

+1

Это юмор или таки понял? Я ж не про поиск последовательности одинаковых букв. Могу сказать что меня редко понимают.. А писать подробно дурной тон..
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #11
Попробуем вот так вот на 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, но лень.
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #12
Это юмор или таки понял? Я ж не про поиск последовательности одинаковых букв. Могу сказать что меня редко понимают.. А писать подробно дурной тон..

Написать можно разными способами, однако чтобы написать самый короткий и быстродействующий способ необходимо подумать. Я правильно вас понял? :)
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #13
Вери спс.
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #14
Насчет быстродействия. Думаю, что пример от уважаемого balkauser можно оптимизировать. :)
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #15
Не буду создавать новую тему, прошу совета в решении задачи сортировки.
есть к примеру массив

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

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

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

Как задать правильно условие для нулей?
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #16
эм... проверяйте, если у вас значение 0 то замените его на 2147483648, после чего пройдитесь в конце по массиву и присвойте значениям 2147483648 значение 0. вариант калечный, но вероятность того, что в вашем массиве будет столь большое число практически нулевая
зы: еще считайте количество нулей в массиве, и заменяйте число 2147483648 на 0 с конца массива, тогда вариант да же будет правильно работать при условии что у вас в массиве да же будут числа равные 2147483648.
 
Останнє редагування:
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #17
Эх, сессия пришла, и ничего умнее чем написать на ХФ в голову не пришло...
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #18
5 коп критики, если не возражаете ...

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

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

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

это теоретическая задача ... посему вероятность встречи такого числа равна вероятности встречи любого числа из диапазона int ...
 
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #19
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;
}

в общем как нить так.
 
Останнє редагування:
  • 🟡 07:30 Відбій тривоги в Харківська область.Зверніть увагу, тривога ще триває у:- Куп’янський район- Харківський район- Липецька територіальна громада- Вовчанська територіальна громада#Харківська_область
  • #20
Не буду создавать новую тему, прошу совета в решении задачи сортировки.
есть к примеру массив

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)
 
Назад
Зверху Знизу