Язык Си в примерах/Система счисления

Число 235 в десятичной системе счисления есть

$235_{10}=2\cdot 10^2+3\cdot 10+5$

Число 235 в восьмеричной системе счисления есть

$235_8=2\cdot 8^2+3\cdot 8+5$

Пусть $Q$ — натуральное число. Тогда представить число $N$ в Q-ичной системе счисления означает представить число $N$ в виде суммы различных степеней $Q$ с целыми коэффициентами из диапазона $[0;Q-1]$:

$N=a_0\cdot Q^0+a_1\cdot Q^1+a_2\cdot Q^2+...$

Q-ичная запись числа $N$ — это набор коэффициентов $(a_m,a_{m-1},...,a_0)$,где $a_m$ — последний ненулевой коэффициент.

Вопросы

1. Докажите методом математической индукции, что это разложение существует и единственно. Для тренировки разберите отдельно случай $Q=2$: любое натуральное число представляется в виде суммы различных степеней двойки и притом единственным образом.

Примеры:

• $1_{10}=1_2$
• $2_{10}=0\cdot 2^0+1\cdot 2^1=10_2$
• $3_{10}=1\cdot 2^0+1\cdot 2^1=11_2$
• $4_{10}=0\cdot 2^0+0\cdot 2^1+1\cdot 2^2=100_2$
• $5_{10}=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2=101_2$
• $15_{10}=1\cdot 2^0+1\cdot 2^1+1\cdot 2^2+1\cdot 2^3=1111_2$
• $16_{10}=0\cdot 2^0+0\cdot 2^1+0\cdot 2^2+0\cdot 2^3+1\cdot 2^4=10000_2$
• $255_{10}=1\cdot 2^0+1\cdot 2^1+1\cdot 2^2+1\cdot 2^3+1\cdot 2^4+1\cdot 2^5+1\cdot 2^6+1\cdot 2^7=11111111_2$

2. Что делает приведённая ниже программа?

#include <stdio.h>
void main ()
{
    int n; 
    scanf ("%d", &n);
    while(n)
    {
        printf("%d", n%2);
        n /= 2;
    }
}

3. Напишите программу, которая введённое натуральное (число в десятичной записи) переводит в восьмеричную систему счисления.