Задача с собеседования

[MrGukk]

Добрый день!

Был сегодня на собеседовании и в качестве задачи было предложено написать следующую программу.

Написать функию, которая принимает на вход строку как аргумент (напр. 1b32apo94), ничего не возвращает, а строку меняет т.о. чтобы сначала стояли буквы, а потом цифры, при этом порядок в котором буквы и цифры встречаются в строке не менять. Для данного примера, правильно работающая программа должна получить:
bapo13294.

Конечно, можно выделить память и за 2 цикла решить задачу, но криво как-то.

Можно ли сделать соответствующие преобразования без выделения памяти?
Хоть примерный алгоритм.

Заранее спасибо.

[MrGukk]

ЗЫ. Язык С++.

[Lesha]

procedure transNum(var s:string);
var
t,t2:string; i:integer;
const num = ['0'..'9'];
begin
  t:=''; t2:='';
  for i :=1 to length(s) do
    if s[i] in num then
      t:=t+s[i]
    else
      t2:=t2+s[i];
  s:=t2+t;
end;

еще можно через сравнение

procedure transNum(var s:string);
var t,t2:string; i:integer;
begin
  t:=''; t2:='';
  for i :=1 to length(s) do
    if (s[i] >= '0') and (s[i] <= '9') then
      t:=t+s[i]
    else
      t2:=t2+s[i];
  s:=t2+t;
end;

незнаю как C++ а на delphi так

[mss]

а на delphi так

И на delphi не так. Совсем не так.
то что ты привел не имеет к "без выделения памяти" ни малейшего отношения.

[Lesha]

ну тогда вот еще
издержки вычислений = 8 байт

procedure transNum(var s:string);
var i,l:integer;
begin
  l:=length(s); i:=1;
  while i<=l do begin
    if (s[i] >= '0') and (s[i] <= '9') then begin
     s:=s+s[i];
     delete(s,i,1);
     l:=l-1;
    end else
     i:=i+1;
  end;
end;

[mss]

ну тогда вот еще

Те же фаберже, только вид сбоку - вновь в коде фигурирует выделение/перераспределение памяти.

[Lesha]

procedure transNum(var s: ShortString);
begin
  s:=char(length(s)+2)+char(3)+s;
  while s[2]<=s[1] do begin
    if (s[byte(s[2])] >= '0') and (s[byte(s[2])] <= '9') then begin
     s:=s+s[byte(s[2])];
     delete(s,byte(s[2]),1);
     s[1]:=char(byte(s[1])-1);
    end else
     s[2]:=char(byte(s[2])+1);
  end;
    delete(s,1,2);
end;

все вычисления строго в строке никаких переменных

[Stilet]

Я бы такое предложил:

var s:string;k,i:integer; c:char;
begin
 s:='1b32apo94';
 for i:=1 to length(s) do for k:=i+1 to  length(s) do begin
  if  (s[i] in ['0'..'9']) then begin
   c:=s[k];s[k]:=s[i];s[i]:=c;
  end;
 end;
 write(s);readln;
  { TODO -oUser -cConsole Main : Insert code here }
end.

все вычисления строго в строке никаких переменных

Если не ошибаюсь delete(s,byte(s[2]),1); и s:=s+s[byte(s[2])]; заставляют срабатывать механизмы перераспределения памяти - создается новая строка.

[Lesha]

срабатывать механизмы перераспределения памяти - создается новая строка

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

[onewho]

автор имеет ввиду, без вставок, только обменами, перемешать последовательность. я так понимаю максимум одна временная переменная.

однако неизвестно что будет эффективней.

и стоило бы указать работаем то со string или char[] ?

ПС: в С++ любое такое действо делается 1ой функцией stable_partition
http://www.cplusplus.com/reference/a...ble_partition/
хотя разумеется ясно что задача дана на алгоритм.

удачи !