Число, Числа больше заданного составленные из тех же цифр Опции

[Ольга]

Вводится некоторое натуральное число N, состоящее не более чем из 8 различных цифр (первая – не 0). Определить, сколько существует различных чисел, больших N и составленных из тех же цифр (и в тех же количествах), что и N.

[volvo]

Насколько я понимаю, твою задачу можно привести к следующему:

1) по заданной перестановке найти ее номер в списке перестановок, упорядоченных лексикографически;
2) определить общее число перестановок, возможное с заданными цифрами;
3) вычесть из второго числа первое (пользуясь тем, что лексикографически упорядоченные перестановки с бОльшими номерами будут давать бОльшие числа).

Тогда тебе сюда: http://alglib.sources.ru/combinatorial/permutations.php

Сообщение отредактировано: volvo - 3.05.2007 20:06

[Ольга]

Большое спасобо за совет. Только помогите практически решить эту задачуб так как в указанной ссылке нет Паскаля, только Делфи и СИ. Буду очень благодарна за Вашу помощь.
Оля.

[Гость]

в указанной ссылке нет Паскаля, только Делфи и СИ

В программе, на Дельфи, приведенной по ссылке, нет ничего, что не компилировалось бы в Паскале... (

var x : TInteger1DArray

можно заменить на

var X: array of integer

)

[Ольга]

Все так и сделала - заменила var x : TInteger1DArray на var X: array of integer. Но там описана только функция, а не знаю куда вставить тело цикла. Пожалуйста, помоги доделать программу.

[samec]

вот что получилось у меня

program perm;
uses CRT;
var
 i,n,kol:Longint;
 x:array[1..8] of integer;

function NextPermutation:Boolean;
var
    k : Integer;
    t : Integer;
    y : Integer;
begin
    
{    //
    // Check
    //}
    if N<=0 then
    begin
        NextPermutation := False;
        Exit;
    end;
    K:=1;
    while K<=N do
    begin
        if (X[K]<1) or (X[K]>N) then
        begin
            NextPermutation := False;
            Exit;
        end;
        Inc(K);
    end;
    
{    //
    // Process
    //}
    k := n-1;
    while k>0 do
    begin
        if x[k]<=x[k+1] then
        begin
            Break;
        end;
        k := k-1;
    end;
    if k<>0 then
    begin
        t := k+1;
        while t<n do
        begin
            if x[t+1]<=x[k] then
            begin
                Break;
            end;
            t := t+1;
        end;
        y := x[k];
        x[k] := x[t];
        x[t] := y;
        t := 0;
        while t<(n-k) div 2 do
        begin
            y := x[n-t];
            x[n-t] := x[k+1+t];
            x[k+1+t] := y;
            t := t+1;
        end;
        NextPermutation := True;
    end
    else
    begin
        NextPermutation := False;
    end;
end;


begin
 write('Введите n:');
 readln(n);
 kol:=0;
 for i:=1 to n do
  begin
   write('введите ',i,'-ую цифру числа: ');
   readln(x[i]);
  end;
 clrscr;
 write('заданное число: ');
 for i:=1 to n do
    write(x[i]);
 writeln;
 writeln;
 while (NextPermutation) do
  begin
   inc(kol);
   write(kol,'-ое число: ');
   for i:=1 to n do
    write(x[i]);
   writeln;
  end;
 writeln('Итого ',kol,' чисел больше заданного');
 write('Нажмите любую клавишу для выхода...');
 readkey;
end.

[Ольга]

Что-то у меня не получается с этой программой. В числе должно быть не более 8 цифр, а программа согласно этой строке write('введите ',i,'-ую цифру числа: '); запрашивает 14 раз 'введите 1-ую цифру числа' и так до 14 раз (хотя, например, ввожу число из 3-х цифр).

[volvo]

Вот так попробуй:

function Fact(n: integer): longint;
var
  i: integer;
  T: longint;
begin
  T := 1;
  for i := 1 to n do T := T * i;
  Fact := T;
end;

function PermutationNum(const A : array of integer; N : Integer): longint;
var
  T, i, j: integer;
  F: longint;
  theResult: longint;
begin
  if N <= 0 then begin
    PermutationNum := 0; Exit;
  end;

  I:=1;
  while I <= N do begin

    if (A[I]<1) or (A[I]>N) then begin
      PermutationNum := 0; Exit;
    end;
    Inc(I);

  end;

  theResult := 0;
  F := 1;
  I := 1;
  while I <= N do begin
    F := F*I;
    Inc(I);
  end;

  I := 1;
  while I <= N-1 do begin
    F := F div (N+1-I);
    T := A[I]-1;
    J := 1;
    while J <= I-1 do begin
      if A[J]<A[I] then begin
        T := T-1;
      end;
      Inc(J);
    end;
    theResult := theResult + F*T;
    Inc(I);
  end;
  theResult := theResult + 1;
  PermutationNum := theResult;
end;

const
  n: integer = 3;
var
  arr: array[0 .. 8] of integer;
  s: string;
  i: integer;
  p, total: longint;

begin
  write('n = '); readln(n);
  write('number[', n, ' chars] = '); readln(s);

  arr[0] := 0;
  for i := 1 to n do arr[i] := ord(s[i]) - ord('0');

  p := PermutationNum(arr, n);
  total := Fact(n);
  writeln(total - p);
end.

(вводишь сначала n - не больше 8, потом в виде строки само число из n цифр...)

Сообщение отредактировано: volvo - 7.05.2007 18:21

[samec]

Что-то у меня не получается с этой программой. В числе должно быть не более 8 цифр, а программа согласно этой строке write('введите ',i,'-ую цифру числа: '); запрашивает 14 раз 'введите 1-ую цифру числа' и так до 14 раз (хотя, например, ввожу число из 3-х цифр).

значит просто ввела n равное не трём, а четырнадцати.

у меня вот как программа работает:

Введите n:3
введите 1-ую цифру числа: 1
введите 2-ую цифру числа: 2
введите 3-ую цифру числа: 3
заданное число: 123

1-ое число: 132
2-ое число: 213
3-ое число: 231
4-ое число: 312
5-ое число: 321
Итого 5 чисел больше заданного
Нажмите любую клавишу для выхода...


Сообщение отредактировано: samec - 8.05.2007 12:11

[Ольга]

Большое спасибо, все правильно работает!!!
Оля