ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи. Ошибка поиска совпадений
32 сообщений из 32, показаны все 2 страниц
  все  
Строки Фибоначчи. Ошибка поиска совпадений
    #38968679
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
#include <iostream>
#include <string>

  using namespace std;

size_t elem_counting( const char *str, const char *substr ) {

	size_t cnt = 0, len = strlen( substr );

	for( ; str = strstr( str, substr ); str = str + len ) {
		cnt++;
	}

	return cnt;
}

int main() {

	const int n = 40;

	string str[46];

	str[0] = "A";
	str[1] = "B";

		for( int i = 2; i < n; i++ ) {
			str[ i ] = str[ i - 1 ] + str[ i - 2 ];
		}

	    cout<<elem_counting(str[35].c_str(),"BBABAB");

	return std::cin.get();
}

/*
  Функция elem_counting не правильно считает количество вхождений.
  Ошибка при n = 45;
*/



Есть у кого-нибудь решение этой задачи ?
...
Рейтинг: 0 / 0
26.05.2015, 14:06
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38968715
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Памяти не хватает, т.к. для 45-й строки надо 1,8 Гб. А ты еще предыдущие хранишь, это еще ~3 Гб.
Вот размеры строк
nбайт40165580141412679142964243349443743701408733441134903170451836311903
...
Рейтинг: 0 / 0
26.05.2015, 14:23
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38968813
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, что думаешь по поводу системы счисления Фибоначчи?
...
Рейтинг: 0 / 0
26.05.2015, 15:08
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38968821
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima T, что думаешь по поводу системы счисления Фибоначчи?
Если честно понятия не имею что это такое ))

Просто посчитал в экселе длину строки для этого цикла
Код: plaintext
1.
2.
3.
for( int i = 2; i < n; i++ ) {
	str[ i ] = str[ i - 1 ] + str[ i - 2 ];
}
...
Рейтинг: 0 / 0
26.05.2015, 15:13
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38968833
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
 
Не нашёл. Где-то было в форуме...
...
Рейтинг: 0 / 0
26.05.2015, 15:21
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970403
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
И как ему быть в таком случае ? Записывать в файл ? Или создавать тип данных особым образом хранящий строки (сжимающий их).
...
Рейтинг: 0 / 0
28.05.2015, 10:07
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970408
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryИ как ему быть в таком случае ? Записывать в файл ? Или создавать тип данных особым образом хранящий строки (сжимающий их).
Ему не нужны строки, ему нужно посчитать вхождение подстроки. Надо хранить не строку, а структуру типа {"N первых символов", кол-во вхождений, "N последних символов"} где N длина подстроки.
...
Рейтинг: 0 / 0
28.05.2015, 10:12
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970462
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Тогда уже и вовсе никаких строк хранить не надо, достаточно убедиться, что начиная с какого-то значения n склеивание строк обязательно добавляет нужную подстроку и просто нужное число раз сложить пару чисел и 1.
...
Рейтинг: 0 / 0
28.05.2015, 11:05
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970568
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
wst,

уважаемый, на примере не покажете ?
...
Рейтинг: 0 / 0
28.05.2015, 12:06
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970751
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
смотрим первые строки такого типа:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
0 B 0
...
5 BABBABABBABBA 1
6 BABBABABBABBABABBABAB 3
7 BABBABABBABBABABBABABBABBABABBABBA 4
8 BABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBABAB 8
...
Видно, что с какого-то момента строки либо кончаются на 'B', тогда в месте склейки получается 'BBABB' либо на 'BBA', тогда в месте склейки получается 'BBABAB', и это дело чередуется. Далее очевидно.
...
Рейтинг: 0 / 0
28.05.2015, 13:45
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970768
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
wst,

а если такая строка BABBABABBABBABABBABABBABB

вот она задача
...
Рейтинг: 0 / 0
28.05.2015, 13:54
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970772
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
wst,

под строка
...
Рейтинг: 0 / 0
28.05.2015, 13:56
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38970897
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Принцип тот же.
...
Рейтинг: 0 / 0
28.05.2015, 15:14
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38974871
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
gera3323,
появилось немного времени. Может быть попробовать решить эту задачу так.
0. Если номер строки меньше 10 решить любым интуитивным 'прямым' способом. Конец.
1. Найти, сколько раз встречается искомая строка в F_9, F_10 ( count9, count10)
2. Используя два счётчика найти итоговый результат. Правда как это сделать пока не додумал. Попробуйте сами. Конец.

Или вы решили эту задачу как-то иначе ?
...
Рейтинг: 0 / 0
03.06.2015, 09:09
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975086
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
SashaMercurygera3323,
появилось немного времени. Может быть попробовать решить эту задачу так.
0. Если номер строки меньше 10 решить любым интуитивным 'прямым' способом. Конец.
1. Найти, сколько раз встречается искомая строка в F_9, F_10 ( count9, count10)
2. Используя два счётчика найти итоговый результат. Правда как это сделать пока не додумал. Попробуйте сами. Конец.

Или вы решили эту задачу как-то иначе ?Одна маленькая проблема: а вдруг подстрока начинается в F_9, а заканчивается в F_10?
...
Рейтинг: 0 / 0
03.06.2015, 11:55
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975233
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
SashaMercurygera3323,
появилось немного времени. Может быть попробовать решить эту задачу так.
0. Если номер строки меньше 10 решить любым интуитивным 'прямым' способом. Конец.
1. Найти, сколько раз встречается искомая строка в F_9, F_10 ( count9, count10)
2. Используя два счётчика найти итоговый результат. Правда как это сделать пока не додумал. Попробуйте сами. Конец.

Или вы решили эту задачу как-то иначе ?

пока не решил. способы подсчетов много нашел. проблема все та же с памятью. сейчас буду решать эту проблему
...
Рейтинг: 0 / 0
03.06.2015, 13:17
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975238
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Ну уже ответили ... 17699895
...
Рейтинг: 0 / 0
03.06.2015, 13:20
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975455
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Barlone, F9 и F10 используются не просто так. Если строки не будет в F10, её не будет нигде, ни в F45.

Я не понял как Дмитрий предложил решать эту задачу. Хочется увидеть алгоритм. У меня пока нет времени заняться ей хотя бы на полчаса.
...
Рейтинг: 0 / 0
03.06.2015, 15:30
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975460
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SSBarlone, F9 и F10 используются не просто так. Если строки не будет в F10, её не будет нигде, ни в F45.

Я не понял как Дмитрий предложил решать эту задачу. Хочется увидеть алгоритм. У меня пока нет времени заняться ей хотя бы на полчаса.
или если её не будет в циклической F8.
...
Рейтинг: 0 / 0
03.06.2015, 15:32
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975479
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЯ не понял как Дмитрий предложил решать эту задачу. Хочется увидеть алгоритм.
Храним строку в виде {"начало", кол-во вхождений, "конец"}
где "начало" это первые символы строки до первого вхождения подстроки, но не более N, где N кол-во символов в подстроке
"конец" это последние символы строки после последнего вхождения, но не более N

Сложение двух строк:
Код: plaintext
1.
2.
{"начало1", кол-во вхождений1, "конец1"} + {"начало2", кол-во вхождений2, "конец2"} =
{"начало1", кол-во вхождений1 + кол-во вхождений в строке ("конец1" + "начало2") + кол-во вхождений2, "конец2"}


Понятно объяснил?

PS Чуть посложнее получилось чем выше писал.
...
Рейтинг: 0 / 0
03.06.2015, 15:54
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975488
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще надо немного допилить для случаев когда нет вхождений и строка меньше 2N.
...
Рейтинг: 0 / 0
03.06.2015, 16:05
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975499
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Должен напомнить, что и начало и конец у строк будут чередоваться, так что можно ничего такого не хранить. Просто доводим строки до такого размера чтобы там уместилась нужная подстрока и проверяем появляется ли эта подстрока на границе при склеивании строк на четных и нечетных итерациях. С этого момента хранить никакие строки больше не нужно и задача сводится к сложению целых чисел (то есть на каждой итерации складываем количества вхождений за 2 предыдущие, дальше смотрим - это четная или нечетная и нужно ли для такой четности учитывать подстроку, появляющуюся в месте склеивания строк, если нужно - еще +1).
...
Рейтинг: 0 / 0
03.06.2015, 16:17
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975583
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
SashaMercuryBarlone, F9 и F10 используются не просто так. Если строки не будет в F10, её не будет нигде, ни в F45.
Это почему? Для произвольной подстроки?
...
Рейтинг: 0 / 0
03.06.2015, 18:03
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975697
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
Dima T,

задачу решил. на сайте http://www.e-olymp.com/ и http://informatics.mccme.ru/ решение засчитано 100%.

но вот в ручную стал проверку делать нашел ошибки. система их не точна.
...
Рейтинг: 0 / 0
03.06.2015, 21:05
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38975698
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
Dima T,

буду добиваться идеального решения.
...
Рейтинг: 0 / 0
03.06.2015, 21:06
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38976899
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
BarloneSashaMercuryBarlone, F9 и F10 используются не просто так. Если строки не будет в F10, её не будет нигде, ни в F45.
Это почему? Для произвольной подстроки?

Нет, для строки длиной 25 символов. Почему ? По причине наличия рекурсии в этой задаче. Нужно нарисовать абстрактную строку, и откатиться в ней назад
...
Рейтинг: 0 / 0
05.06.2015, 01:52
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38976900
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryЯ не понял как Дмитрий предложил решать эту задачу. Хочется увидеть алгоритм.
Храним строку в виде {"начало", кол-во вхождений, "конец"}
где "начало" это первые символы строки до первого вхождения подстроки, но не более N, где N кол-во символов в подстроке
"конец" это последние символы строки после последнего вхождения, но не более N

Сложение двух строк:
Код: plaintext
1.
2.
{"начало1", кол-во вхождений1, "конец1"} + {"начало2", кол-во вхождений2, "конец2"} =
{"начало1", кол-во вхождений1 + кол-во вхождений в строке ("конец1" + "начало2") + кол-во вхождений2, "конец2"}


Понятно объяснил?

PS Чуть посложнее получилось чем выше писал.

и тогда мы не превысим лимит по памяти ?
...
Рейтинг: 0 / 0
05.06.2015, 01:55
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38976902
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
BarloneSashaMercurygera3323,
появилось немного времени. Может быть попробовать решить эту задачу так.
0. Если номер строки меньше 10 решить любым интуитивным 'прямым' способом. Конец.
1. Найти, сколько раз встречается искомая строка в F_9, F_10 ( count9, count10)
2. Используя два счётчика найти итоговый результат. Правда как это сделать пока не додумал. Попробуйте сами. Конец.

Или вы решили эту задачу как-то иначе ?Одна маленькая проблема: а вдруг подстрока начинается в F_9, а заканчивается в F_10?

Значит использовать вариант с циклической F8.
...
Рейтинг: 0 / 0
05.06.2015, 01:57
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38976921
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryи тогда мы не превысим лимит по памяти ?
Прикинь сам сколько байт надо для хранения одной такой строки.
...
Рейтинг: 0 / 0
05.06.2015, 06:59
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38976968
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryи тогда мы не превысим лимит по памяти ?
Прикинь сам сколько байт надо для хранения одной такой строки.
Больше чем можно
...
Рейтинг: 0 / 0
05.06.2015, 08:51
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38977747
gera3323
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gera3323
Участник
ну дак что ее решил кто-нибудь ?
...
Рейтинг: 0 / 0
05.06.2015, 18:38
| Ответить | Цитировать | Написать  
Строки Фибоначчи. Ошибка поиска совпадений
    #38977857
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Какие-то на сайте с задачей кривые компиляторы и способ подсчета затрат памяти. Что на std::stoi, что на auto ругаются "ошибка компиляции". Да и затраты памяти вообще без динамических выделений и менее чем 300 байт расхода стека без учета printf и scanf превратились в 1100+КБ.
...
Рейтинг: 0 / 0
05.06.2015, 22:38
| Ответить | Цитировать | Написать  
32 сообщений из 32, показаны все 2 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи. Ошибка поиска совпадений
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]