Logo MurCode
C++ Новое сообщение

Строки Фибоначчи

gera3323
Дата: 06.06.2015 21:08:37 
#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;
};



Так никто и не решил эту задачу ? я сделал, ее засчитала система. при ручном подсчете я вижу что она считает не правильно. как сделать не знаю. всяко перепробовал
wst
Дата: 07.06.2015 08:38:55
Короче, думаю спустя такое время можно выложить один из вариантов решения. Оно в итоге было принято (пришлось, правда, здорово урезать язык), но с какой-то стати расходу памяти ему больше мегабайта насчитали:
+ кто собирается решать сам - сюда не тыкать
Да, да, в коде остались некоторые артефакты вроде int l2=1;...l2=2, не говоря уже о местах объявления переменных, но чистить лень.
#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);
}
SashaMercury
Дата: 09.06.2015 01:52:38
gera3323,
зачем переменным типа int в параметрах функции вы применяете квалификатор const ?
Повторите ваш код с комментариями к функциям, пожалуйста
SashaMercury
Дата: 09.06.2015 02:46:38
А можно все сообщения переместить в один топик ? Зачем два создали, gera3323 ?
SashaMercury
Дата: 10.06.2015 03:05:59
Проверьте, у меня нет учетной записи на том ресурсе.
Кстати, судя по тестовым примерам, строки могут пересекаться.

// 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;
}
SashaMercury
Дата: 10.06.2015 03:50:29
wst,
посмотрел сейчас ваш код, не стал сильно вникать, но судя по всему алгоритмы похожи
wst
Дата: 10.06.2015 08:56:02
SashaMercury,

Алгоритмы действительно основаны на одной идее, но есть один момент:
f[0].s = (char*)malloc(sizeof(char)*(f[0].num + 1));
f[0].s = "a";
- memory leak, однако.
И по условиям задачи номер строки и подстрока для поиска читаются из стандартного ввода, так что или "+odd%2" - слишком смелое предположение в общем случае или безусловное присваивание "odd=0".
SashaMercury
Дата: 11.06.2015 02:49:35
wst
SashaMercury,

Алгоритмы действительно основаны на одной идее, но есть один момент:
f[0].s = (char*)malloc(sizeof(char)*(f[0].num + 1));
f[0].s = "a";
- memory leak, однако.
И по условиям задачи номер строки и подстрока для поиска читаются из стандартного ввода, так что или "+odd%2" - слишком смелое предположение в общем случае или безусловное присваивание "odd=0".


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

Комментарий относительно odd не понял
wst
Дата: 11.06.2015 08:54:40
SashaMercury

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

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


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

Насчет odd повторюсь - "...подстрока для поиска читаются из стандартного ввода". Примеры для тестирования: AB, BA, BB.
SashaMercury
Дата: 11.06.2015 10:17:35
Согласен с замечанием :) Тогда так.
// 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 это просто вспомогательная переменная. Для подсчёта в том случае, когда подстрока встречается в циклической строке. Потому не понимаю в чём проблема