Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Строки Фибоначчи / 19 сообщений из 19, страница 1 из 1
06.06.2015, 21:08
    #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
| Ответить | Цитировать | Написать  
07.06.2015, 08:38
    #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
| Ответить | Цитировать | Написать  
09.06.2015, 01:52
    #38979662
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи
gera3323,
зачем переменным типа int в параметрах функции вы применяете квалификатор const ?
Повторите ваш код с комментариями к функциям, пожалуйста
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.06.2015, 02:46
    #38979672
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи
А можно все сообщения переместить в один топик ? Зачем два создали, gera3323 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.06.2015, 03:05
    #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:50
    #38980635
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи
wst,
посмотрел сейчас ваш код, не стал сильно вникать, но судя по всему алгоритмы похожи
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.06.2015, 08:56
    #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
| Ответить | Цитировать | Написать  
11.06.2015, 02:49
    #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, 08:54
    #38981807
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи
SashaMercury
Утечка тут в том, что в конце программы я не освободил память. Что легко устраняется.

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

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

Насчет odd повторюсь - "...подстрока для поиска читаются из стандартного ввода". Примеры для тестирования: AB, BA, BB.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.06.2015, 10:17
    #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:46
    #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, 11:02
    #38981946
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Строки Фибоначчи
wst,
теперь приблизительно понятно что вы мне хотите сказать. odd название условное, обратите внимание, что все циклы идут по одной переменной i, потому повторения в местах склейки будут считаться как на чётных, так и на нечётных позициях.

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


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