Чистая математика

[Guest_guest]

Определена функция f(0) = 1, f(1) = 1
f(2n) = f, f(2n+1) = f + f(n+1)

Для заданного натурального числа M найти f(M)

посоветуйте, как это можно реализовать.

 

[Guest]

Если с рекурсией, то просто -

int f(int p)
{
if (p <= 0)
return 0;
if (p == 1)
return 1;
if (p & 1)
return (f(p/2) + f(p/2+1));
return f (p/2);
}


А вот без рекурсии надо больше повозиться.

 

[Guest]

<!--QuoteBegin-Guest+18:02:2005, 11:06 -->
<span class="vbquote">(Guest @ 18:02:2005, 11:06 )</span><!--QuoteEBegin-->Если с рекурсией, то просто -

int f(int p)
{
if (p <= 0)
return 0;
if (p == 1)
return 1;
if (p & 1)
return (f(p/2) + f(p/2+1));
return f (p/2);
}


А вот без рекурсии надо больше повозиться.[/quote]
без желательно

 

[Guest]

<!--QuoteBegin-QUOTE+Guest-->
<span class="vbquote">(QUOTE @ Guest)</span><!--QuoteEBegin-->Если с рекурсией, то просто -

int f(int p)
{
if (p <= 0)
 return 0;
if (p == 1)
 return 1;
if (p & 1)
 return (f(p/2) + f(p/2+1));
return f (p/2);
}


А вот без рекурсии надо больше повозиться.[/quote]

int event (int );
int it (int );


int main (int argc, char **argv)
{
 int i;
 
 int m = 5;
 
 int temp = 0;
 for (i = 1; i <= it(m); ++i )
   {      
     if (m%2 == 1) temp +=  event(m/2) + event(m/2 + 1);
     else temp += event(m/2);
     
   }
 
  printf("%d", temp); 

}


int event(int m)
{
 if(m==1) return 1;
 if(m==0) return 0;
 else return m;
}

int it (int M)
{
 int i;
 for (i = 1;; i++)
   {
     M /= 2;
     if (M == 1) break;
   }
 return i;
}

посмотрите плз. что я делаю неправильно, подскажете кто че сможет.
сильно ногами не пинать.

 

[Guest]

У тебя вроде как какая-то ерунда написана, или я просто не понял подхода. it(М) - степень двойки, ближайшая к М. И что?
Я наверняка туплю, это должно делаться проще, но я бы с первого подхода сделал так (если надо без рекурсии):

int F(int M)
{
CStack<int> s;
s.Push(M);
DWORD dwCur = 0;
while (!s.IsEmpty())
{
  int nTop = s.Pop();
  if (nTop == 0)
   continue;
  if (nTop == 1)
 {
   dwCur++;
   continue;
  }
  s.Push(nTop/2);
  if (nTop & 1)
   s.Push (nTop/2+1);
}
 return dwCur; 
}

Стек какой-нибудь сам напишешь. Но, имхо, без стека тут не обойтись. Можно еще последовательно считать F(0,1,...M), храня все результаты, но это памяти потребует много.

 

[Guest]

<!--QuoteBegin-Guest+21:02:2005, 11:17 -->
<span class="vbquote">(Guest @ 21:02:2005, 11:17 )</span><!--QuoteEBegin-->У тебя вроде как какая-то ерунда написана, или я просто не понял подхода. it(М) - степень двойки, ближайшая к М. И что?
Я наверняка туплю, это должно делаться проще, но я бы с первого подхода сделал так (если надо без рекурсии):

int F(int M)
{
CStack<int> s;
s.Push(M);
DWORD dwCur = 0;
while (!s.IsEmpty())
{
  int nTop = s.Pop();
  if (nTop == 0)
   continue;
  if (nTop == 1)
 {
   dwCur++;
   continue;
  }
  s.Push(nTop/2);
  if (nTop & 1)
   s.Push (nTop/2+1);
}
 return dwCur; 
}

Стек какой-нибудь сам напишешь. Но, имхо, без стека тут не обойтись. Можно еще последовательно считать F(0,1,...M), храня все результаты, но это памяти потребует много.[/quote]
Спасибо за помощь, то что я писал действительно чушь

Я просто хотел вычилить кол-во итераций необходимое для вычисления функции, а затем в цикле вызывать функцию.