ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи
19 сообщений из 19, страница 1 из 1
Строки Фибоначчи
    #38978241
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.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>

	using namespace std;

unsigned int getFib( const int bIndex, const int eIndex ) {

	unsigned int result[ 46 ] = { 1, 1 };
	
	int Index = eIndex - bIndex ;

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

	return result[ Index ];
}

string getTail( const string &str, const string &substr ) {
	return str.substr( str.size() - (substr.size() - 2), substr.size() - 1);
}

string getHead( const string &str, const string &substr ) {
	return str.substr( 0, substr.size() - 1);
}

unsigned int calc( const char *str, const char *substr ) {

	size_t cnt    = 0;
	size_t offset = strlen( substr );

	char *ptr = const_cast<char*>( str );

	while ( ptr = strstr( ptr, substr ) ) {
		*ptr = *ptr + offset - 1; cnt++;
	}

	return cnt;
}

unsigned int getcalc( const string &sequence, int Index ) {

	string result[ 50 ] = { "A", "B" };

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

	if( sequence.size() == 1 ) {
		return ( Index < 2 ) ? (( result[ Index - 1 ] == sequence ) ? 1 : 0 ) : (sequence == "A") ? getFib( 3, Index ) : getFib( 2, Index );
	}

	Index--;

	int cnt = 0;

	if( Index < 10 ) {

		return calc( result[ Index ].c_str(), sequence.c_str() );

	} else {

		for( int i = 2; i < 10; i++ )
		{
			if( result[ i ].find( sequence ) != string::npos )
			{
			//	cout<< getTail( result[ i - 1 ], sequence ) + getHead(result[ i - 2 ], sequence)<<endl;

				return getFib( i, Index + 1) - calc( (getTail( result[ i - 1 ], sequence ) + 
					getHead(result[ i - 2 ], sequence )).c_str(), sequence.c_str() );
			}
		}
	}

	return 0;
}

int main( void )
{
	ifstream if_file("input.txt");
	ofstream of_file("output.txt");

	string sequence;
	int Index;


    if_file>>Index>>sequence; of_file<<getcalc( sequence, Index )<<endl;
	

	of_file.close();
	if_file.close();

	return 0;
};




Так никто и не решил эту задачу ? я сделал, ее засчитала система. при ручном подсчете я вижу что она считает не правильно. как сделать не знаю. всяко перепробовал
...
Рейтинг: 0 / 0
06.06.2015, 21:08
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38978317
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Короче, думаю спустя такое время можно выложить один из вариантов решения. Оно в итоге было принято (пришлось, правда, здорово урезать язык), но с какой-то стати расходу памяти ему больше мегабайта насчитали:
 
кто собирается решать сам - сюда не тыкатьДа, да, в коде остались некоторые артефакты вроде int l2=1;...l2=2, не говоря уже о местах объявления переменных, но чистить лень.
Код: 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.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
#include <stdio.h>

int scount(const char * buf, const char * ss) {
  int res = 0;
  for(const char * start = buf, *ptr = buf, *ptr2; *ptr; ++start) {
    ptr = start;
    ptr2 = ss; 
    while( *ptr && *ptr2 && *ptr == *ptr2) {
      ++ptr;
      ++ptr2;
    }
    if(!*ptr2) {
      ++res;
    }
  }
  return res;
}

int main() {
  char substring_to_count[26];
  int N = 0;
  scanf("%d\n%s", &N, substring_to_count);

  char buf[90] = {0, };
  int l1 = 1;
  int l2 = 1;

  long long res = 0;
  if(1 == N) {
    res = scount("A", substring_to_count);
  } else if(2 == N) {
    res = scount("B", substring_to_count);
  } else {
    long long count[11] = {
      0,//step = 0
      scount("A", substring_to_count),
      scount("B", substring_to_count),
      };
    buf[0] = 'B';
    buf[1] = 'A';
    l2 = 2;
    for(int step = 3; step < 11 && step <= N; ++step) {
      count[step] = scount(buf, substring_to_count);
      for(int ofs = 0; ofs != l1; ++ofs) {
        buf[l2 + ofs] = buf[ofs];
      }
      int new_len = l1 + l2;
      l1 = l2;
      l2 = new_len;
    }
    buf[l2] = 0;
    if(N < 11) {
      res = count[N];
    } else {
      long long d[2] = {
        count[9] - count[8] - count[7],
        count[10] - count[9] - count[8],
      };
      int c1 = count[9];
      int c2 = count[10];
      for(int step = 10; step < N; ++step) {
        int t = c1 + c2 + d[step % 2];
        c1 = c2;
        c2 = t;
      }
      res = c2;
    }
  }
  printf("%lld\n", res);
}

...
Рейтинг: 0 / 0
07.06.2015, 08:38
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38979662
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
gera3323,
зачем переменным типа int в параметрах функции вы применяете квалификатор const ?
Повторите ваш код с комментариями к функциям, пожалуйста
...
Рейтинг: 0 / 0
09.06.2015, 01:52
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38979672
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А можно все сообщения переместить в один топик ? Зачем два создали, gera3323 ?
...
Рейтинг: 0 / 0
09.06.2015, 02:46
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38980634
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Проверьте, у меня нет учетной записи на том ресурсе.
Кстати, судя по тестовым примерам, строки могут пересекаться.

Код: 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.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
// Fibostrings.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE 10 //количество чисел

//Числовые и строковые значения Фибоначчи
struct Fib
{
	int num;
	char* s;
} fib[SIZE];

//вычисление целочисленных и символьных значений Fib
int calculate_fib_arrays(struct Fib* f)
{
	f[0].num = 1;
	f[0].s = (char*)malloc(sizeof(char)*(f[0].num + 1));
	f[0].s = "a";
	f[1].num = 1;
	f[1].s = (char*)malloc(sizeof(char)*(f[1].num + 1));
	f[1].s = "b";
	for (int i = 2; i < SIZE; ++i){
		f[i].num = f[i - 1].num + f[i-2].num;
		f[i].s = (char*)malloc(sizeof(char)*(f[i].num + 1));
		memcpy(f[i].s, f[i - 1].s, f[i-1].num);
		memcpy(f[i].s + f[i - 1].num, f[i - 2].s, f[i - 2].num + 1);
	}
	return 0;
}

//прямой поиск подстроки в строке
int direct_search(char* s,  const char* ss)
{
	int count = 0;
	char* cur = s;
	size_t size_ss = strlen(ss);
	while ((cur = strstr(cur, ss))){
		++count;
		++cur;
		//cur += size_ss;
	}
	return count;
}


int main()
{
	//input data
	char* substring = "bbabab";
	int len_FS = 34;
	size_t len_ss = strlen(substring);
	//calculate auxiliary data
	calculate_fib_arrays(fib);
	//MAIN ALGORITHM
	int res = 0;
	if (len_FS <= 10){
		res = direct_search(fib[len_FS].s, substring);
	}
	else{
		int f=0, s=0, t=0;//first, second, third
		int i = 0;
		while (!f && i<SIZE){
			f = direct_search(fib[i].s, substring);
			++i;
		}
		if (f){//if smth founded
			s = direct_search(fib[i].s, substring);
			t = direct_search(fib[i+1].s, substring);
		}
		//analysing data
		int res_prev = t;
		int res_prevprev = s;
		if (t == f + s){
			for (int j = i + 1; j < len_FS; ++j){
				res = res_prev + res_prevprev;
				res_prevprev = res_prev;
				res_prev = res;
			}
		}
		else{
			int odd = 0;
			for (int j = i + 1; j < len_FS; ++j){
				res = res_prev + res_prevprev + odd%2;
				res_prevprev = res_prev;
				res_prev = res;
				++odd;
			}
		}
	}
	printf("res=%i\n",  res);
	return 0;
}
...
Рейтинг: 0 / 0
10.06.2015, 03:05
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38980635
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
wst,
посмотрел сейчас ваш код, не стал сильно вникать, но судя по всему алгоритмы похожи
...
Рейтинг: 0 / 0
10.06.2015, 03:50
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38980698
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
SashaMercury,

Алгоритмы действительно основаны на одной идее, но есть один момент:
Код: plaintext
1.
2.
f[0].s = (char*)malloc(sizeof(char)*(f[0].num + 1));
f[0].s = "a";

- memory leak, однако.
И по условиям задачи номер строки и подстрока для поиска читаются из стандартного ввода, так что или "+odd%2" - слишком смелое предположение в общем случае или безусловное присваивание "odd=0".
...
Рейтинг: 0 / 0
10.06.2015, 08:56
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38981758
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
wstSashaMercury,

Алгоритмы действительно основаны на одной идее, но есть один момент:
Код: plaintext
1.
2.
f[0].s = (char*)malloc(sizeof(char)*(f[0].num + 1));
f[0].s = "a";

- memory leak, однако.
И по условиям задачи номер строки и подстрока для поиска читаются из стандартного ввода, так что или "+odd%2" - слишком смелое предположение в общем случае или безусловное присваивание "odd=0".

Утечка тут в том, что в конце программы я не освободил память. Что легко устраняется.

Комментарий относительно odd не понял
...
Рейтинг: 0 / 0
11.06.2015, 02:49
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38981807
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
SashaMercury
Утечка тут в том, что в конце программы я не освободил память. Что легко устраняется.

Комментарий относительно odd не понял

Ок, хотелось бы увидеть пример как "в конце программы" освободить память, выделенную для f[0].s?

Насчет odd повторюсь - "...подстрока для поиска читаются из стандартного ввода". Примеры для тестирования: AB, BA, BB.
...
Рейтинг: 0 / 0
11.06.2015, 08:54
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38981887
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Согласен с замечанием :) Тогда так.
Код: 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.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
// Fibostrings.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE 10 //количество чисел

//Числовые и строковые значения Фибоначчи
struct Fib
{
	int num;
	char* s;
} fib[SIZE];

//вычисление целочисленных и символьных значений Fib
int calculate_fib_arrays(struct Fib* f)
{
	f[0].num = 1;
	f[0].s = (char*)malloc(sizeof(char)*(f[0].num + 1));
	   f[0].s[0] = 'a'; f[0].s[1] = '\0';
	f[1].num = 1;
	f[1].s = (char*)malloc(sizeof(char)*(f[1].num + 1));
	   f[1].s[0] = 'b'; f[1].s[1] = '\0';
	for (int i = 2; i < SIZE; ++i){
		f[i].num = f[i - 1].num + f[i-2].num;
		f[i].s = (char*)malloc(sizeof(char)*(f[i].num + 1));
		memcpy(f[i].s, f[i - 1].s, f[i-1].num);
		memcpy(f[i].s + f[i - 1].num, f[i - 2].s, f[i - 2].num + 1);
	}
	return 0;
}

void free_fib(struct Fib* f)
{
	for (int i = 0; i < SIZE; ++i){
		free(f[i].s);
	}
}

//прямой поиск подстроки в строке
int direct_search(char* s,  const char* ss)
{
	int count = 0;
	char* cur = s;
	size_t size_ss = strlen(ss);
	while ((cur = strstr(cur, ss))){
		++count;
		++cur;
		//cur += size_ss;
	}
	return count;
}



int main()
{
	//input data
	char* substring = "bbabab";
	int len_FS = 34;
	size_t len_ss = strlen(substring);
	//calculate auxiliary data
	calculate_fib_arrays(fib);
	//MAIN ALGORITHM
	int res = 0;
	if (len_FS <= 10){
		res = direct_search(fib[len_FS].s, substring);
	}
	else{
		int f=0, s=0, t=0;//first, second, third
		int i = 0;
		while (!f && i<SIZE){
			f = direct_search(fib[i].s, substring);
			++i;
		}
		if (f){//if smth founded
			s = direct_search(fib[i].s, substring);
			t = direct_search(fib[i+1].s, substring);
		}
		//analysing data
		int res_prev = t;
		int res_prevprev = s;
		if (t == f + s){
			for (int j = i + 1; j < len_FS; ++j){
				res = res_prev + res_prevprev;
				res_prevprev = res_prev;
				res_prev = res;
			}
		}
		else{
			int odd = 0;
			for (int j = i + 1; j < len_FS; ++j){
				res = res_prev + res_prevprev + odd%2;
				res_prevprev = res_prev;
				res_prev = res;
				++odd;
			}
		}
	}
	printf("res=%i\n",  res);
	free_fib(fib);
	return 0;
}




odd это просто вспомогательная переменная. Для подсчёта в том случае, когда подстрока встречается в циклической строке. Потому не понимаю в чём проблема
...
Рейтинг: 0 / 0
11.06.2015, 10:17
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38981916
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Если рассматривать как задачу поиск только подстроки "bbabab", то с odd все правильно, однако исходная задача была более общая и допускает необходимость поиска подстрок, которые будут появляться в местах склейки не на нечетных шага, а на четных. Пример с AB, BB, BA - как раз к тому что у этих трех подстрок разные условия образования в местах склеивания. Если дополнительная BA не появляется нигде (все строки кроме первой начинаются с B), то две другие получаются на разных по четности номера итерациях. В последнем же варианте кода подстроки, появляющиеся на четных итерациях будут обработаны в ветке
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
		if (t == f + s){
			for (int j = i + 1; j < len_FS; ++j){
				res = res_prev + res_prevprev;
				res_prevprev = res_prev;
				res_prev = res;
			}
		}

, то есть некорретно. То есть в текущей логике odd сам по себе используется корректно, но сам способ прихода в эту ветку не вполне корректен в общем случае.
...
Рейтинг: 0 / 0
11.06.2015, 10:46
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38981946
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
wst,
теперь приблизительно понятно что вы мне хотите сказать. odd название условное, обратите внимание, что все циклы идут по одной переменной i, потому повторения в местах склейки будут считаться как на чётных, так и на нечётных позициях.

Ну если я и сейчас неправ, то приведите контрпример пожалуйста, я его внимательно изучу. Спасибо :)
...
Рейтинг: 0 / 0
11.06.2015, 11:02
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38981962
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
На то, что циклы в конце начинаются с i я до сих пор не обращал внимания, возражения снимаются, был неправ.
...
Рейтинг: 0 / 0
11.06.2015, 11:11
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #38982006
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Хорошо, спасибо за замечания:)
...
Рейтинг: 0 / 0
11.06.2015, 11:33
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Строки Фибоначчи
    #39499323
stut
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stut
Участник
Вот спрошу о рекурсии без новой темы. Прочитал на днях что использование рекурсии для чисел фибоначчи может привести к зависанию програмы уже для числа n=100, если использовать типовую формулу: int fib(int n) { if n<2 return 1; return fib(n-1) + fib(n-2); } и была предложена в начале какая то невиданная для меня формула if (0==numbers[n] {numbers[n]= Fib[n-1] + Fib[n-2]; } return numbers[n]; Как это 0== ... и та же рекурсия?
...
Рейтинг: 0 / 0
02.08.2017, 23:13
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #39501030
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
stutВот спрошу о рекурсии без новой темы. Прочитал на днях что использование рекурсии для чисел фибоначчи может привести к зависанию програмы уже для числа n=100, если использовать типовую формулу: int fib(int n) { if n<2 return 1; return fib(n-1) + fib(n-2); } и была предложена в начале какая то невиданная для меня формула if (0==numbers[n] {numbers[n]= Fib[n-1] + Fib[n-2]; } return numbers[n]; Как это 0== ... и та же рекурсия?

0 в левой части, поскольку используется одна из практик для предотвращения непреднамеренного присваивания. Здесь ленивая динамика, предварительно все элементы массива инициализируются SMTH_DEFAULT_VALUE, на второй итерации рассчитываются все элементы вплоть до требуемого n, либо это таблица формируется заранее. Линейное время О(n), никакой рекурсии, никаких деревьев
...
Рейтинг: 0 / 0
06.08.2017, 23:10
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #39501388
stut
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stut
Участник
SashaMercury,
а что реально зависает програма расчета рекурсии? Не в одном учебнике этот подход приведеный.
...
Рейтинг: 0 / 0
07.08.2017, 16:37
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #39501584
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Возможно речь идет о рекурсии "с хвостиком" ?.
...
Рейтинг: 0 / 0
08.08.2017, 00:03
| Ответить | Цитировать | Написать  
Строки Фибоначчи
    #39502503
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
stut,
рекурсивный алгоритм имеет асимптотику (F(n+1)/F(n))^n~1.6^n, при n <-100 вы получите порядка const*10^20 операций
...
Рейтинг: 0 / 0
09.08.2017, 12:44
| Ответить | Цитировать | Написать  
19 сообщений из 19, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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