Сначала мы пишем a[0] = a[1] = 1;
Дальше мы пробегаем циклом с 2 до n. Если i четное тогда вычисляем a[i] с помощью формулы которая нам дана в условии : a[i] = a[i / 2] + a[(i / 2) - 1]. Если i нечетное, тогда делаем то же самое только вычисляем разность. И в конце выводим a[n].