Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи. Ошибка поиска совпадений / 25 сообщений из 32, страница 1 из 2
  1  все
26.05.2015, 14:06
    #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:23
    #38968715
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
Памяти не хватает, т.к. для 45-й строки надо 1,8 Гб. А ты еще предыдущие хранишь, это еще ~3 Гб.
Вот размеры строк
nбайт40165580141412679142964243349443743701408733441134903170451836311903
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.05.2015, 15:08
    #38968813
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
Dima T, что думаешь по поводу системы счисления Фибоначчи?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.05.2015, 15:13
    #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:21
    #38968833
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
 
Не нашёл. Где-то было в форуме...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.05.2015, 10:07
    #38970403
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
И как ему быть в таком случае ? Записывать в файл ? Или создавать тип данных особым образом хранящий строки (сжимающий их).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.05.2015, 10:12
    #38970408
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
SashaMercuryИ как ему быть в таком случае ? Записывать в файл ? Или создавать тип данных особым образом хранящий строки (сжимающий их).
Ему не нужны строки, ему нужно посчитать вхождение подстроки. Надо хранить не строку, а структуру типа {"N первых символов", кол-во вхождений, "N последних символов"} где N длина подстроки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.05.2015, 11:05
    #38970462
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
Тогда уже и вовсе никаких строк хранить не надо, достаточно убедиться, что начиная с какого-то значения n склеивание строк обязательно добавляет нужную подстроку и просто нужное число раз сложить пару чисел и 1.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.05.2015, 12:06
    #38970568
gera3323
gera3323
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
wst,

уважаемый, на примере не покажете ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.05.2015, 13:45
    #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:54
    #38970768
gera3323
gera3323
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи. Ошибка поиска совпадений
wst,

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

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

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

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

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

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

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

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

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

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

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

буду добиваться идеального решения.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи. Ошибка поиска совпадений / 25 сообщений из 32, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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