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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Guest_guest, 18 фев 2005.

Статус темы:
Закрыта.
  1. Guest_guest

    Guest_guest Гость

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

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

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

    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);
    }


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

    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]
    без желательно
     
  4. Guest

    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]
    Код (Text):
    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;
    }
    посмотрите плз. что я делаю неправильно, подскажете кто че сможет.
    сильно ногами не пинать.
     
  5. Guest

    Guest Гость

    У тебя вроде как какая-то ерунда написана, или я просто не понял подхода. it(М) - степень двойки, ближайшая к М. И что?
    Я наверняка туплю, это должно делаться проще, но я бы с первого подхода сделал так (если надо без рекурсии):
    Код (Text):
    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), храня все результаты, но это памяти потребует много.
     
  6. Guest

    Guest Гость

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

    Я просто хотел вычилить кол-во итераций необходимое для вычисления функции, а затем в цикле вызывать функцию.
     
Загрузка...
Похожие Темы - Чистая математика
  1. NickProstoNick
    Ответов:
    7
    Просмотров:
    3.456
  2. acorn
    Ответов:
    9
    Просмотров:
    13.038
Статус темы:
Закрыта.

Поделиться этой страницей