Программистская задача

[spamsink]

Старая, но хорошая. Для интервью, пожалуй, сложновасто, а как головоломка сгодится.

Дан целый массив, про который известно, что его элементы имеют значения в диапазоне от 0 до 7 включительно и весь он представляет одно большое восьмеричное число (концеватость по вкусу). Написать программу, которая переводит это число в десятичный вид (с той же концеватостью), используя O(1) дополнительной памяти.

Comments

[gmz.livejournal.com]

Уточнение: новое число должно быть в том же самом массиве?

[spamsink]

Да, разумеется. Иначе условие использование константного количества дополнительной памяти не будет выполнено.

[avs313.livejournal.com]

Считаем с большого конца по стандартной схеме (взяли первую цифру, умножили на 8, добавили очередную, и так пока цифры не закончатся). Т.к. 10 > 8, то освободившихся за ненадобностью элементов массива как раз хватит для хранения десятичного вида.

[spamsink]

Массив может быть длиной в несколько сотен или тысяч элементов.

[avs313.livejournal.com]

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

[spamsink]

Алгоритм, разумеется, будет квадратичный, но обычно в подобных задачах требуется "не зюзюкать, а пальцем показать".

[ivan-ghandhi.livejournal.com]

Easy. Но странно, как одни и те же идеи болтаются в воздухе; я то же самое обдумывал с утра (вчера).

[spamsink]

Естественно, ничего особенно сложного в этом нет, но что-то никто не решается привести код. Или трюк, благодаря которому это пишется в 5 строк, широко известен?

[avs313.livejournal.com]

ну код так код
кстати, про 5 строчек интересно, у меня сильно больше получилось

#include "stdio.h"

int main()
{
const int N = 10;
const int BASE1 = 8;
const int BASE2 = 10;
int arr[N];
int i;
for (i = 0; i < N; i++) arr[i] = 1;
arr[7] = 2;
for (i = 1; i < N; i++)
{
int v = arr[i]; arr[i] = 0;
for (int j = 0; j <= i; j++)
{
v += arr[j] * BASE1;
arr[j] = v % BASE2;
v /= BASE2;
}
}
return 0;
}

как тест забито (8^10 - 1) / (8 - 1) + 8^2 = (1 111 111 211)_8 = 153391753_10

[avs313.livejournal.com]

да, забыл написать - начальные данные в big endian, результат - в little

[spamsink]

Нет, так не годится. По вкусу, но у данных и результата должны совпадать.

[avs313.livejournal.com]

тоже мне проблема
for (i = 0; i < (N / 2); ++i) swap(a[i], a[N - 1 - i]);
и все
перед return само собой

[spamsink]

Конечно, но строчки, строчки... :) Вечером напишу свое решение.

[avs313.livejournal.com]

для меня это будет уже утро
жду :)

Квадратичное время

[ygam.livejournal.com]

o2d [] = []
o2d (ol:oh) = decplus ol (mul8dec (o2d oh))

Re: Квадратичное время

[ygam.livejournal.com]

Ой, не работает: стек линейный.

Re: Квадратичное время

[ygam.livejournal.com]

Работает: нам стек не нужен.

Сейчас напишу код.

[ygam.livejournal.com]

// Given an integer represented as an array of base-10 digits, multiply it by 8
// and add another number.
// The integer to multiply begins with digit 1; the number to add is at digit 0;
// the result begins with digit 0.
void mul8decshiftadd (unsigned char digits[], int n)
{
    unsigned char carry = digits[0];
    digits[0] = 0;
    for (int i=1;  i<n;  i++)
    {
        digits[i-1] += (8*digits[i])%10;
        digits[i] = (8*digits[i])/10;
    }
    for (int i=0;  i<n;  i++)
    {
        unsigned char nextCarry = (carry+digits[i])/10;
        digits[i] = (carry+digits[i])%10;
        carry = nextCarry;
    }
}

// Given an integer represented as an array of base-8 digits, transform it to base 10.
void octal2decimal (unsigned char digits[], int n)
{
    for (int m=n-1;  m>=0;  m--)
    {
        mul8decshiftadd (digits+m, n-m);
    }
}

[skavish.livejournal.com]

так будет немного покороче, хотя должен признать что тут немного больше используется памяти :)

  void mul8decshiftadd(unsigned char digits[], int n) {
    int carry = digits[0];
    for (int i = 1; i < n; i++) {
      int sum = carry + 8 * digits[i];
      digits[i - 1] = sum % 10;
      carry = sum / 10;
      digits[i] = carry % 10;
    }
  }