Максимальная непрерывная сумма в двоичном дереве за N переходов

#алгоритм #дерево #теория

Дано двоичное дерево, со значениями весов перехода.
Нужно получить максимальное значение за N переходов начиная с нулевого узла. При
этом путь должен быть непрерывный,с бесплатными возвратами в родительский узел.

Мой текущий алгоритм:


Найти последний доступный узел(в котором количество ходов равно 0, либо отсутствуют
дети).  
Записать в массив текущее значение и количество доступных ходов(с учетом потомков).
Перейти в родительский узел, скопировать оба массива(если 2 потомка), либо 1 массив
(1 потомок).
Повторять п.2-3 до возврата в корневой узел.
На основании массива в корневом узле (в котором находятся все
возможные сочетания значений+ходов) найти максимальное значение.


Основные вопросы:


Существует ли лучший алгоритм?
Возможно ли оптимизировать данный алгоритм т.к. работает слишком
долго и требует слишком много памяти?

    

Ответы

Ответ 1

Решение за N*S памяти, N*S*S или N*S*log S времени. S - размер дерева.

Динамика F[vert][size] - оптимальный ответ если мы в поддереве вершины vert берём
size элементов.

Для любого элемента F[u][0] = 0
Для листа на этом всё. 

Для вершины псевдокод. (r - правый потомок, l - левый).

for (int i=0;i
Ответ 2

Собственно ответ,возможно пригодится кому-то:
В дереве всегда добавляю сначала левую ноду , затем правую(см. if(left!=NULL & right==NULL).

void getMax(Node *curr,int turns)
{
    int i,j;
    if(curr->left!=NULL && turns!=0)
        getMax(curr->left,turns-1);
    if(curr->right!=NULL && turns!=0)
        getMax(curr->right,turns-1);
    curr->res=new int[turns+1]();
    curr->res[0]=0;
    if(curr->left==NULL && curr->right==NULL || turns==0)
    {
        for(i=1;ires[i]=0;
        return;
    }
    else
    {
        if(curr->left!=NULL && curr->right==NULL)
        {
            Node*next=curr->left;
            for(i=0;ires[i+1]=next->res[i]+next->value;
            }
        }
        else
        {
                Node *left=curr->left;
                Node *right=curr->right;
                for(i=0;ires[0]=0;
                            }
                            if(i==0 && j>=1)
                            {
                                curr->res[j]=max(curr->res[j],right->value+right->res[j-1]);
                            }
                            if(i>=1 && j==0)
                            {
                                curr->res[i]=max(curr->res[i],left->value+left->res[i-1]);
                            }
                            if(i>=1 && j>=1)
                            {
                                curr->res[i+j]=max(curr->res[i+j],left->value+right->value+left->res[i-1]+right->res[j-1]);
                            }

                    }
                }
    }
}
}


и сам класс

class Node
{
public:
Node *parent;
Node *left;
Node *right;
int id;
int value;
int *res;};

Ошибка spring security на wildfly

#java #spring #spring_security #spring_boot #wildfly

При логине в приложение на spring-security выдает следующее сообщение:    

{"timestamp":1464679377206,"status":999,"error":"None","message":"No message available"}


и редиректит на error-page в приложении развернутом на wildfly, при запуске spring-boot
такой проблемы нет. При чем, если затем вбить правильный адрес руками все работает
корректно.
Класс запуска приложения:

@SpringBootApplication
public class Application extends SpringBootServletInitializer {

    public static void main(String[] args) throws Exception {
        SpringApplication.run(Application.class, args);
    }

    @Override
    protected SpringApplicationBuilder configure(SpringApplicationBuilder application) {
        return application.sources(applicationClass);
    }

    private static Class applicationClass = Application.class;

}


Thymeleaf форма логина

        

        

            

                
            
            

                
            
            
        


Security configuration

@Configuration
@EnableWebSecurity
public class WebSecurityConfig extends WebSecurityConfigurerAdapter {

    @Autowired
    UserService userService;

    @Autowired
    @Qualifier("userServiceImpl")
    UserDetailsService userDetailsService;

    @Autowired
    public void configureGlobalSecurity(AuthenticationManagerBuilder auth) throws
Exception {
        auth.userDetailsService(userDetailsService);
    }

    @Override
    protected void configure(HttpSecurity http) throws Exception {
        http
                .authorizeRequests()
                .antMatchers("/", "/home", "/signup", "/add_person").permitAll()
                .anyRequest().authenticated()
                .and()
                .formLogin()
                .loginPage("/login")
                .permitAll()
                .and()
                .logout()
                .permitAll();
    }

    @Override
    public void configure(WebSecurity web) throws Exception {
        web.ignoring()
                .antMatchers("/images/**");
    }
}


UPD: 
debug
FirewalledRequest[ HttpServletRequestImpl [ GET /PersonalFinance/error ]]
Похоже на какую-то ошибку фаервола, хотя не уверен, что это рут кос. Как отключить
фаервол на debian?

Логи смотрел — там ничего.



Нашел пару вопросов по этой теме на eng.so:


Spring Security with basic auth redirecting to /error for invalid credentials
Spring Security - Remember Me Authentication Error


Но ни один из представленных там ответов не решил проблему.
    

Ответы

Ответ 1

Ошибка появлялась из-за того, что папка с картинками не была включена в проект, но
была прописана в spring-security конфигурации. Соответственно, эту папку спринг не
находил и ругался.

Ссылка на дочерние элементы в layout с merge

#android #include #merge

Здравствуйте,

сделал свой аналог numericUpDown, т.е. поле с двумя кнопками, которые увеличивают
или уменьшают значение. Одна и та же разметка довольно часто используется, поэтому
хотел бы на нее ссылаться с помощью include и merge. 

Есть следующий файл разметки reference_linear_layout_up_down_numeric_buttons: 


>

 
 




В основном меню идет отсылка на разметку reference_linear_layout_up_down_numeric_buttons:

  


Как теперь можно в java программе сослаться на кнопки ?

Например если я напишу вот так:

  View  mView_LayoutView = findViewById(R.id.layoutUpDownNumerOfStars);

  Button mButtonUp = mView_LayoutView.findViewById(R.id.buttonArrowUp);


То компилятор выдает ошибку NullPointerException.

Если написать вот так:

  Button mButtonUp = findViewById(R.id.buttonArrowUp);


То будет неоднозначная ситуация например если несколько ссылок в основной разметке
на разметку reference_linear_layout_up_down_numeric_buttons с кнопками. 

Как в этом случае нужно правильно сослаться на кнопки в java программе?

Заранее большое спасибо всем за ответы.
    

Ответы

Ответ 1

Получить ссылку на merge нельзя. Используется он (как я понял из доков) для возможности
заменить 2 include 1 merge.

Засим, отличить кнопки из merge друг от друга можно лишь по их родителю. Т.е. нельзя
поместить два идетичных merge в один контейнер. Ведь в этом случае у вас будет один
и тот же ID у нескольких элементов.

Но вы можете поместить по одному merge в разные контейнеры в одной общей разметке
и находить их через эти контейнеры.

containerView.findViewById(...).;

Метод штрафных функций

#python #алгоритм #математика

Привет!

Пытаюсь реализовать метод штрафных функций для вычисления минимума функции. Ищу минимум
функции Розенброка, минимизирую с помощью внешних штрафных функций:



придумав свои ограничения. Сначала использую встроенную scipy.optimize.minimize:

from scipy.optimize import minimize, rosen
rz = lambda x: (1-x[0])**2 + 100*(x[1] - x[0]**2)**2;
h_1 = lambda x: (x[0] - 2 * x[1] + 2);
h_2 = lambda x: (-x[0] - 2 * x[1] + 6);
h_3 = lambda x: (-x[0] + 2 * x[1] + 2);

x0 = [2.3, 5];
cons = ({'type': 'ineq', 'fun': h_1},
       {'type': 'ineq', 'fun': h_2},
       {'type': 'ineq', 'fun': h_3}) 
minimize(rz, x0, constraints=cons)


Которая даёт ответ: x: array([ 0.99971613,  0.99942073])

Затем пытаюсь реализовать метод штрафных функций:

x_c = [2.3, 3];
i = 1;
while i < 1000:
    curr_func = lambda x: rz(x) + i*(h_1(x)**2 + h_2(x)**2 + h_3(x)**2)
    x_c = minimize(curr_func, x_c).x;
    i  *= 1.2;
print(answer.x);


Что выводит мне [ 2.27402022  1.4157964 ] (если увеличивать количество итераций,
точка будет ещё с большими координатами).

Где я ошибаюсь в реализации?
Спасибо.

P.S. Окончательная функция curr_func специфична для конкретно приведённых ограничений,
конечно, когда все они типа inequals.
    

Ответы

Ответ 1

Не всегда увеличение количества итераций даст лучший результат, особенно в методах
оптимизации. Как правило крутить надо параметры, которые отвечают за штраф или начальные
точки, если конечно правильно реализован алгоритм. Еще один момент - надо задать точность
результата, и из цикла лучше все-таки выходить, когда результат достигнет точности.

Я поправил ваш алгоритм, пользуясь этой статьей

 x_c = [2.3, 3]
 i = 1
 r = 1
 b = 0.2
 eps = 0.01
 while i < 1000:
     if curr_func(x_c) < eps:
         break
     curr_func = lambda x: rz(x) + r*(1.0/(h_1(x)**2 + h_2(x)**2 + h_3(x)**2))
     x_c = minimize(curr_func, x_c).x;
     i += 1
     r  *= b;
print(x_c)
print(i)
[ 0.99495003  0.98991398]
3


получаем результат всего за 3 итерации.

Как работают функции с переменным числом аргументов в C?

#c #функции #переменные

Навеяно вопросом Как работает execlp, что за последний аргумент NULL? Полистал ответы
на схожие вопросы, но подробного описания не нашёл:


Функции с переменным числом параметров
Как в C объявить функцию с переменным числом аргументов?
С и переменное число аргументов


И т.д.

P.S Предполагается, что читатель этого текста уже выпустился из детсада, и не задаёт
вопросов уровня "Мне тут какую-то ошибку выдали, чо это?". И не путает C с C++.

Пинки, подзатыльники и прочие указания на "ты неправ" приветствуются.
    

Ответы

Ответ 1

В языке C есть возможность объявлять и использовать функции с переменным числом аргументов.
Возможность эта обеспечивается особенностями работы со стеком при вызове функций, но
сейчас они подробно рассматриваться не будут, только практическая сторона вопроса.
Магия, происходящая в  тоже за рамками, любопытный да найдёт объяснение этому
шаманству. 

Прототип такой функции может выглядеть так, например:

void print_messages( const char * title, ... );


А вызов - так:

print_messages( "Вот что имею сообщить", 
                "это раз", "это два", "это три", NULL );


И печатать, соответственно:

Вот что имею сообщить:
 - это раз.
 - это два.
 - это три.


Ну и её реализация:

void print_messages( const char * title, ... ) {

    va_list ap;
    const char * message;
    va_start( ap, title );

    printf( "%s:\n", title );

    message = va_arg( ap, const char * );
    while( message ) {
        printf( " - %s.\n", message );
        message = va_arg( ap, const char *);
    }

    va_end( ap );
}


Самой важной проблемой тут является определение конца списка аргументов. В данном
случае использовался NULL для его отметки. Но это не всегда приемлемо. Например, когда
NULL является допустимым значением аргумента. Или, скажем, 0/-1 в случае целых чисел. 

Первое решение этой проблемы - передать количество аргументов первым параметром:

void print_numbers( size_t amount, ... ) {

    va_list ap;
    int number;
    va_start( ap, amount );

    printf( "Total numbers: %zu, let's go! ", amount );
    while( amount-- ) {
        number = va_arg( ap, int );
        printf( " [%d]", number );
    }

    va_end( ap );
}


Вызов:

print_numbers( 3, 11, 22, 33 );


Этот метод может применяться только тогда, когда в функцию передаются аргументы одного
типа. Того же можно добиться, передавая массив значений с его размером. Но это не всегда
оправдано. Да и рассматривается сейчас технологическая демка, а не целесообразность
(которая всегда на совести программиста, но на то к нему /dev/brain и прилагается). 

Шёпотом: ну и TMTOWTDI в сях тоже бывает, хи-хи...

А что делать, если аргументы могут быть разных типов? Тут на помощь приходит метод
под названием "формат". Любой сишник с ним знаком по *printf*. Но это не интересно.
Придумаем своё, на том же принципе.

Определимся:


символ 'c' означает char
's' - short
'l' - long
'z' - char *


Прототип:

void print_something( const char * format, ... );


Реализация:

 void print_something(const char * fmt, ...) {

  va_list ap;
  va_start( ap, fmt );
  /* Гусары, молчать! */
  long l;
  int i;
  char c;
  char *z;


  while( *fmt ) {

    switch( *fmt ) {
        case 'c':
            /* см дальше */
            c = (char)va_arg( ap, char );
            printf( "char: '%c'\n", c );
            break;

        case 's':
            /* см дальше */
            s = (short)va_arg( ap, short );
            printf( "short: '%d'\n", s );
            break;

        case 'i':
            i = va_arg( ap, int );
            printf( "int: '%d'\n", i );
            break;

        case 'l':
            l = va_arg( ap, long );
            printf( "long: '%lu'\n", l );;
            break;

        case 'z':
            z = va_arg( ap, char * );
            printf( "char *: '%s'\n", z );;
            break;

        default:
            printf( "Хрен знает что передали: '%c'\n", *fmt );
            break;
    }
    fmt++;
  }
}


Дальше: char, short и прочее, которое меньше int.

Эти строчки возбуждают компилятор:

c = (char)va_arg( ap, char );
/* 'char' is promoted to 'int' when passed through '...' */
s = (short)va_arg( ap, short );
/* 'short' is promoted to 'int' when passed through '...' */


Выводы делать не буду, оставлю на домашнее задание.

Как правильно выставить права для /var/www/?

#linux #apache2 #permissions

Первый случай production сервер, второй для разработки.
    

Ответы

Ответ 1

На продакшене и на сервере разработки должно быть всё одинаково (ИМХО). Оптимально
755 на папки и 644 на файлы - причём овнер: пользователь, под которым крутится апач,
это www или www-data обычно.


Ответ 2

Поставьте каталогу chmod 2775 и группу chown .www-data.
Теперь новые файлы в этом каталоге будут иметь группу каталога (подробнее о первой
цифре chmod).
Себя добавьте в группу www-data:

sudo adduser $USER www-data.


Установите umask 2, чтобы новые файлы были автоматически доступны группе. Хотя теперь
вы сможете делать файлам в этом каталоге chmod 664 сами без привилегий.

Чтобы задействовалось новое членство в группе нужно войти в систему заново.

Дополнительная функциональность raw_input

#python #python_2x #python_27

Пишу утилиту, которая позволяет запускать определенные скрипты на удаленных машинах.
В итоге, получается что-то вроде ограниченной командой строки. На данный момент я использую
такую конструкцию:

exec_script = raw_input('\033[1;37mcmd> \033[1;m')


Однако в таком варианте кучу неудобств. Например, нельзя использовать клавишу ↑ для
просмотра предыдущих команд. Можно ли это осуществить в python 2.7?
    

Ответы

Ответ 1

Для этого можно воспользоваться модулем readline. Достаточно просто импортировать
его в начале скрипта:

# -*- encoding: utf8 -*-

import readline

while True:
    s = raw_input('\033[1;37mcmd> \033[1;m')
    if s == 'quit':
        print 'Bye bye!'
        break
    print 'Echo: "%s"' % s