j00820. 折半递推数列 · 林老师的题库

题目描述

数列 $a$ 满足： $a_{0} = 0$ ， $a_{1} = 1$ ；当下标为偶数时 $a_{2 m} = a_{m}$ ，下标为奇数时 $a_{2 m + 1} = a_{m} + a_{m + 1}$ 。求 $a_{n}$ 。

一行一个整数 $n$ 。

一行一个整数， $a_{n}$ 的值。

输入

输出