Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.04.2014, 18:26   #21
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
если я всё правильно понял
Ну да
Решить кардинально и "в лоб"
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 07.04.2014, 18:38   #22
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Цитата:
Сообщение от Stilet Посмотреть сообщение
Ну да
Решить кардинально и "в лоб"
Прекращай выпендриваться.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 07.04.2014, 20:51   #23
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

согласитесь код
Код:
#include <fstream>
#include <vector>
#include <string>

using namespace std;

int T = 40;

vector<int> fib(T + 1, 0);
vector<int> fsum(T + 1, 0);

int level(int n) {
  for (int i = 1; ; ++i) {
    if (fsum[i - 1] < n && n <= fsum[i])
      return i;
  }
}

string path(int n) {
  string p;
  for (int j = n; j >= 2;) {
    int l = level(j);
    if (j <= fsum[l - 1] + fib[l - 1]) {
      p += "l";
      j -= fsum[l - 3];
    } else {
      p += "r";
      j -= fsum[l - 1];
      if (j > 2)
        p += "u";
    }
    j -= 2;
  }
  return p;
}

int main() {
  fstream s("input.txt"), q("output.txt",2);
  int n; s >> n;

  fib[1] = 1;
  fib[2] = 2;
  for (int i = 3; i <= T; ++i)
    fib[i] = fib[i - 1] + fib[i - 2];
    
  for (int i = 1; i <= T; ++i)
    fsum[i] = fsum[i - 1] + fib[i];

  string p = path(n);

  vector<int> r(1, 1);

  int t = 1;
  for (int i = 0; i < p.length(); ++i) {
    int jump = p[i] == 'r' ? 1 : 0;
    int l = level(t);
    int next_level_start = fsum[l] + 1;
    int current_level_offset = t - (fsum[l - 1] + 1);
    for (int j = T; j >= 1; --j) {
      int f = fib[j];
      if (f <= current_level_offset) {
        jump += fib[j + 1];
        current_level_offset -= f;
      }
    }
    t = next_level_start + jump;
    r.push_back(t);
  }

  for (int i = r.size() - 1; i >= 0; --i) {
    q << r[i];
    if (i > 0) q << " ";
  }
}
Размер кода: 887
выглядит страшновато
(код не мой!- чтоб ни кто не придрасля)
kostan3 вне форума Ответить с цитированием
Старый 07.04.2014, 20:57   #24
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
Нужно создать что-то вида дерева.. Рекурсивно.. Других идей нет..
да на первый взгляд (и на взгляд на лутшие попытки ) задачу можно решить в 1 цикл
kostan3 вне форума Ответить с цитированием
Старый 07.04.2014, 21:02   #25
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Не стал загружаться в консоль. По-диагонали глянул, роде, критических ошибок нет.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 07.04.2014, 21:08   #26
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

Цитата:
Сообщение от Smitt&Wesson Посмотреть сообщение
Не стал загружаться в консоль. По-диагонали глянул, роде, критических ошибок нет.
мне не нужны ошибки, ошибки я найду сам , нужен боле короткий код
или идея
kostan3 вне форума Ответить с цитированием
Старый 07.04.2014, 21:19   #27
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Цитата:
Сообщение от kostan3 Посмотреть сообщение
мне не нужны ошибки, ошибки я найду сам , нужен боле короткий код
или идея
Зачем? Комп тормозит?
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 07.04.2014, 21:25   #28
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Ну я ж грю, ищи магию чисел

Лично мне приложенный код, впринципе, нравится. Весьма логичное решение. Я пришел к похожему. Искать какие-то загадочные последовательности лично мне не очень интересно.

Легко заметить, что каждый узел дает один узел на следующий уровень и один узел на последующий. Ну посмотри на картинку на acmp (рис. 1).
Поэтому число узлов (l) на уровне N выражается как
l(N - 1) + l(N-2) Ну а это и есть числа Фибоначчи (вобщем про них ИМХО дальше можно забыть - на acmp пишут про фибоначчиеву систему счисления, но я не стал оплавлять мозг).

Дальше? - дальше ты имея номер узла можешь определить его позицию на уровне - очевидно от номера надо отнять количество элементов на всех предыдущих уровнях - автор твоего кода зачем то заводит для этого еще один контейнер, но это опять же l(N-1) + 1 вроде бы.

Смотри на дерево. Ну на acmp тоже дерево, но оно там мелкое и неудобное. Я нарисовал свое (прикрепил). У него явно выделяется левое и правое поддерево (смотри от корня) - различия у них глобальные и количество элементов сильно отличается - поэтому их стоит обрабатывать по-разному.

Правое поддерево меньше и его размер совпадает с l(N-1) - ну оно же очевидно, ведь это то же дерево, но на один ярус меньше).

Короче рубишь дерево до тех пор, пока она не станет равной 1.

Взял ты вершину 75, например, смотришь что оно в 8 ярусе, что относится к правому поддереву относительно корня, отрубил нахрен все что слева и рассматриваешь дерево с корнем в вершине 6.

А че там в один цикл... я хз, если решишь - покажи. МБ это и забавно, но к произвольной задаче не применится. Я чето ниразу никакой фибоначчиевой СС не пользовался.

Цитата:
rrrFer, Я так понимаю, в преобразованиях матиц в деревья и наоборот, Вы не очень. Любую матрицу, можно представить деревом, и любое дерево - матрицей. Закон транзакций.
Звучит так, как будто холодными зимними вечерами вы занимаетесь преобразованием матриц в деревья.
Да я вообще не очень. Что угодно можно представить чем угодно, особенно если речь идет обо всяких абстрактных матрицах и деревьях. Что дальше? Вы о чем, вообще? Приведите пример.

Цитата:
Закон транзакций.
Чето с терминологией у вас не очень. Тут уже просили ссылку на "открытый граф". Вы ссылаетесь на "какую-то там литературу", но никто ее не читал, походу. Что такое закон транзакций?
Насколько я помню из курса ВУЗа (баз данных и не только), транзакция - это группа операций, которая должна быть либо полностью выполнена, либо отменена. Типа, переводишь ты деньги, у тебя деньги взяли, и в этот момент моргнул свет - деньги не дошли куда надо. Чтобы этого не было - группу операций с деньгами называют транзакцией и если моргул свет - то деньги вернут назад (ведь она не была выполнена до конца). Дак вот, чё такое закон транзакций и причем тут преобразование деревьев в матрицы?
Изображения
Тип файла: jpg unnamed0.jpg (87.0 Кб, 139 просмотров)

Последний раз редактировалось rrrFer; 07.04.2014 в 21:36.
rrrFer вне форума Ответить с цитированием
Старый 07.04.2014, 21:34   #29
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Там числа Фиббоначи и небольшие циклы по высчитыванию позиций. А вы докторская Набросал и даже работает вр.0,012 56Кб. По размеру не парился, наверно можно сократить
Код:
program Project1;

{$APPTYPE CONSOLE}

var b,n: array[0..40] of Longint;
    x,m,i,j,k,f,g: Longint;
begin
  reset(input,'input.txt');
  read(x);
  rewrite(output,'output.txt');
  m:=0; i:=0; f:=0; g:=1; b[0]:=1; n[0]:=0;
  while m<x do begin
    Inc(i);
    b[i]:=f+g;
    f:=g;
    g:=b[i];
    Inc(m,g);
    n[i]:=m-g+1;
  end;
  for j:=i downto 1 do begin
    Write(x,' ');
    f:=0;
    Dec(x,n[j]-1);
    while x>0 do
      for k:=j downto 1 do
        if x>=b[k] then begin
          Inc(f,b[k-1]);
          Dec(x,b[k]);
          Break;
        end;
    x:=n[j-1]+f-1;
  end;
end.
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 07.04.2014, 21:37   #30
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Дак вот, че такое закон транзакций и причем тут преобразование деревьев в матрицы?
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск