nombres dont les chiffres sont tous différents [PYTHON]

[invite049950e2]

Bonjour,

J'ai un devoir maison à faire dont voici l'intitulé :

"Trouver tous les nombres composés de chiffres tous différents entre 1 et 100 000."

Mon idée était de créer une liste avec tous les chiffres entre 1 et 100 000 et faire une boucle de n variant entre 0 et 9. Ensuite faire une boucle si n n'est pas plusieurs fois dans le chiffre de la liste alors ajouter ce chiffre à une nouvelle liste.

Je ne suis déjà pas sûre que mon idée soit bonne et en plus je ne sais pas comment faire pour savoir si un chiffre est plusieurs fois dans un nombre.

Serait-il possible de m'aider ?

Je vous remercie d'avance.

Cordialement,
-----

[erik]

" je ne sais pas comment faire pour savoir si un chiffre est plusieurs fois dans un nombre."

12255 y'a 2 fois deux et deux fois cinq.
12345678 tout les chiffres sont sont différrents


comment est ce tu as faits sur pour repondre ? fait la la meme chose pour pondre ton algo

[invite049950e2]

Est-ce que je peux dire qu'un nombre c'est une liste ?

[Garion]

Alors, moi je commencerait par traiter les nombres comme des chaines de caractères.

J'aurai une première boucle pour traiter les nombres en fonction du nombre de chiffres qu'ils contiennent (de 1 à 5)

Dans cette boucle, j'ai une fonction récursive qui ajoute un nouveau chiffre parmi ceux qui n'ont pas été utilisé (ça nécessite, un tableau représentant les chiffres, et un autre tableau de booléen de même taille qui dit si le chiffre a déjà été utilisé).

Ce n'est pas l'algo le plus simple, mais c'est à mon avis assez élégant en terme de compacité et de performance.

Mais ton algo fonctionne aussi (et sera facile à traiter si tu utilises des chaines de caractères), et il y en a de nombreux autres.

[A voir en vidéo sur Futura]

[mp3dux]

Bonjour,



"Trouver tous les nombres composés de chiffres tous différents entre 1 et 100 000."

bonjour, cela aussi comprend le fait que si on écrit 12 on doit pas mettre 21 ?

[invite9dc7b526]

le choix d'un algorithme va être différent selon qu'on veut lister ces nombres dans l'ordre croissant ou pas.

[invite049950e2]

Non je pense que c'est vraiment que dans un même nombre qu'on ne peut pas avoir des chiffres semblables (enfin il me semble...).

[mp3dux]

l'idée du string est intéressante,
tu trouves combien de nombres et tu mets combien de temps pour les 100 000 ?

[Garion]

l'idée du string est intéressante,
tu trouves combien de nombres et tu mets combien de temps pour les 100 000 ?

Je viens de le programmer, mais en Delphi, pas en Pyhton que je ne connais pas bien.
32490 nombres en 2.2ms

[Garion]

Correction, je n'ai pas compté le nombre 100 000. Ça fait donc un de plus.

[Garion]

Correction bis : j'ai fait une boulette entre la conversion ticks et millisecondes, ça fait plutôt 1.15ms

[Garion]

710ms pour les nombres 10 chiffres

[invite9dc7b526]

mon programme met 0.000ms pour énumérer tous les nombres de 11 chiffres (et aussi ceux de 456119324545 chiffes) tous différents.

[Garion]

mon programme met 0.000ms pour énumérer tous les nombres de 11 chiffres (et aussi ceux de 456119324545 chiffes) tous différents.

Si tu avais lu l'énoncé, tu aurais compris que les nombres à 11 chiffres ne peuvent pas exister...
Bon courage troll.

[invite78edc2d4]

Je pense pas que faire une liste avec 100K nombres est une bonne idée, je te conseille de faire une boucle comme ceci:

n=0
while n<100000:
n+=1

Après pour chaque nombre n tu vas le convertir en STRING puis tu vas le divisé en unités dans une liste en utilisant la fonction SPLIT (EX: '56876' >> '5', '6', '8', '7', '6').
Enfin, en utilisant la fonction COUNT tu peux définir la fréquence de chaque unité dans la liste :

f=0
for i in 'liste':
f += 'liste'.count(i)

Si tous les nombres te donne 1 dans la fonction COUNT alors c'est un nombre qui ne présente pas de répétition dans ces unités. un exemple pour vérifier si tous les nombres donne 1:

f=0
for i in 'liste':
f+= 'liste'.count(i)
if f == len(list):
print(n) // un nombre qui répond à ton exercice
else:
continue

[Garion]

Mon programme en Delphi pour LE secptique :
(les temsp que j'ai donné sont pour un i7-920@4Ghz d'il y a 9 ans).

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,
  System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls,
  System.Diagnostics;

const
  NbDeChiffreMax = 10;

type
  TChiffres = Array [0 .. 9] of char;
  Tdisponibilite = array [-1 .. 9] of boolean;

  TFormMain = class(TForm)
    ButtonCalcule: TButton;
    Memo1: TMemo;
    Panel1: TPanel;
    procedure ButtonCalculeClick(Sender: TObject);
  private
    { Déclarations privées }
    Chiffres: TChiffres;
    Liste: TStringList;
    procedure InitialiseChiffres;
    procedure InitialiseDisponibilite(var Disponibilite: Tdisponibilite);
    Procedure AjouteChiffre(Nombre: String; NbChiffresRestant: Integer;
      Disponibilite: Tdisponibilite; DernierChiffre: Integer);
  public
    { Déclarations publiques }
  end;

var
  FormMain: TFormMain;

implementation

{$R *.dfm}

procedure TFormMain.AjouteChiffre(Nombre: String; NbChiffresRestant: Integer;
  Disponibilite: Tdisponibilite; DernierChiffre: Integer);
var
  i: Integer;
  NombreCourant: string;
begin
  Disponibilite[DernierChiffre] := False;
  for i := 0 to 9 do
    // Cas particulier du premier Chiffre qui ne doit pas être égal à 0
    if not((DernierChiffre = -1) and (i = 0)) and Disponibilite[i] then
    begin
      NombreCourant := Nombre + Chiffres[i];
      if NbChiffresRestant <> 1 then
        AjouteChiffre(NombreCourant, NbChiffresRestant - 1, Disponibilite, i)
      else
        Liste.Add(NombreCourant)
    end;
end;

procedure TFormMain.ButtonCalculeClick(Sender: TObject);
var
  i: Integer;
  Nombre: string;
  Disponibilite: Tdisponibilite;
  Stopwatch: TStopwatch;
begin
  // Créer la liste destinée à recevoir les résultats
  Stopwatch := TStopwatch.StartNew;
  Liste := TStringList.Create;
  Liste.Clear;
  Liste.Capacity := 8877690;
  // Prepare la liste de chiffres disponible
  InitialiseChiffres;

  // On démarre à 1 car les nombres de zéro chiffre n'existent pas
  for i := 1 to NbDeChiffreMax do
  begin
    // Tous les chiffres sont disponibles
    Nombre := '';
    InitialiseDisponibilite(Disponibilite);
    AjouteChiffre(Nombre, i, Disponibilite, -1);
  end;
  ShowMessage(FloatToStr(Stopwatch.ElapsedTicks/10000));
  Liste.free;
end;

procedure TFormMain.InitialiseChiffres;
var
  i: Integer;
begin
  for i := 0 to 9 do
    Chiffres[i] := IntToStr(i)[1];
end;

procedure TFormMain.InitialiseDisponibilite(var Disponibilite: Tdisponibilite);
var
  i: Integer;
begin
  for i := 0 to 9 do
    Disponibilite[i] := True;
end;

end.

[mp3dux]

Mon programme en Delphi pour LE secptique :
710ms pour les nombres 10 chiffres
(les temsp que j'ai donné sont pour un i7-920@4Ghz d'il y a 9 ans).
.

Ok, j'ai aussi 32491 nombres, pour le temps d’exécution je sais pas pour delphi mais en python sans parallélisme (l’exécution se déroule sur un seul cœur logique)
224 ms
ryzen 7 1700 3.6 GHz

[invite6486d7bd]

6ms sur de l'Intel Pentium Dual E2180 2GHz

unit Principal;

{$mode objfpc}{$H+}

interface

uses
  Classes,
  SysUtils,
  FileUtil,
  Forms,
  Controls,
  Graphics,
  Dialogs,
  StdCtrls, ExtCtrls;

//*************************************//
//** Type Nombre                     **//
//*************************************//
type TNombre = record
  c     : array of integer;
  lgt   : integer;
end;

type
  { TMain }

  TMain = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    ListBox1: TListBox;
    procedure Button1Click(Sender: TObject);
    procedure FormShow(Sender: TObject);
  private
    { private declarations }
    procedure Initialisation();
    procedure RechercheNombres();
    procedure IncrementeNombre();
    procedure InitialiseNombre();
  public
    { public declarations }
  end;

var
  Main                   : TMain;               // Fiche
  TableauDoublon         : array of boolean;    // Tableau pour détection des chiffres (symboles) en double
  TableauTrouve          : array of integer;    // Tableau des Nombres sans doublon trouvé
  NbSymboles             : integer;             // Nombre de Symboles employés dans un "nombre"
  NbNombre               : integer;             // Nombre de nombres testés
  NbTrouve               : integer;             // Nombre de Nombres sans doublon trouvés
  Nombre                 : TNombre;             // Nombre sur lequel est effectué le travail de recherche
  NbChiffresMaxParNombre : integer;             // Nombre de chiffres max dans le nombre de travail

const
  C_DEFAUT_CAPTION1   = 'Nombre de Nombres Trouvés';

implementation

{$R *.lfm}

{ TMain }

//****************************************************************************//
//** Initialise le Nombre de travail                                        **//
//****************************************************************************//
procedure TMain.InitialiseNombre();
begin
 Nombre.lgt:=1;
 setlength(Nombre.c, NbChiffresMaxParNombre);
 Nombre.c[0]:=0;
end;

//****************************************************************************//
//** Initialisation au premier affichage de la Fiche Main                   **//
//****************************************************************************//
procedure TMain.Initialisation();
begin
  NbSymboles:=10;
  NbNombre:=100000;
  NbChiffresMaxParNombre:=length(IntToStr(NbNombre));
  NbTrouve:=0;
  setlength(TableauDoublon, NbSymboles);
  setlength(TableauTrouve, NbNombre);

  ListBox1.Clear();
  Label1.Caption:=C_DEFAUT_CAPTION1;
end;

//****************************************************************************//
//** Incrémente le Nombre de Travail                                        **//
//****************************************************************************//
procedure TMain.IncrementeNombre();
var
  finretenue  : boolean;
  pc          : integer;
begin
  inc(Nombre.c[0], 1);
  if Nombre.c[0]>9 then
    begin
      pc:=0;
      finretenue:=false;
      repeat
        Nombre.c[pc]:=0;
        inc(pc, 1);
        if pc>=Nombre.lgt then inc(Nombre.lgt, 1);
        inc(Nombre.c[pc], 1);     // Chiffre suivant
        if Nombre.c[pc]<=9 then finretenue:=true;
      until finretenue;
    end;
end;

//****************************************************************************//
//** Recherche des Nombres ne présentant pas de symbole en doublon          **//
//****************************************************************************//
procedure TMain.RechercheNombres();
var
  i,j,k        : integer;
  doublon      : boolean;
begin
  InitialiseNombre();

  NbTrouve:=0;
  for i:=1 to NbNombre do
    begin
      for j:=0 to NbSymboles-1 do TableauDoublon[j]:=false;  // Reset tableau des indicateurs de doublon
      IncrementeNombre();

      k:=0;
      doublon:=false;
      repeat
        if TableauDoublon[Nombre.c[k]] then
          begin
            doublon:=true;
          end
        else
          begin
            TableauDoublon[Nombre.c[k]]:=true;
            inc(k, 1);
          end;
      until doublon or (k>=Nombre.lgt);

      if not doublon then
        begin
          TableauTrouve[NbTrouve]:=i;
          inc(NbTrouve, 1);
        end;
    end;
end;

procedure TMain.FormShow(Sender: TObject);
begin
  Initialisation();
end;

procedure TMain.Button1Click(Sender: TObject);
var
  i,k : integer;
begin
  ListBox1.Clear();
  for k:=1 to 1000 do RechercheNombres();   // On refait le calcul 1000 fois pour mesurer les performances à la louche
  if NbTrouve>0 then
    begin
      setlength(TableauTrouve, NbTrouve);
      for i:=0 to NbTrouve-1 do ListBox1.Items.add(inttostr(TableauTrouve[i]));
    end;
  Label1.Caption:=C_DEFAUT_CAPTION1 + ' : '+inttostr(NbTrouve)
end;

end.

[mp3dux]

6ms sur de l'Intel Pentium Dual E2180 2GHz

Très rapide, je savais pas que delphi était aussi rapide, je connais pas ce langage

y=0
for x de 0 à 1000000
y=x+8

Tu peux juste mesurer combien de temps tu fais cette boucle ?
tu ajoutes 8 à x et enregistres dans y 1 million de fois
mon ordi met 164 ms en python

[invitebb943ab6]

langage EEA : 2 lignes de code, 115 ms (compilation comprise).

[invite9dc7b526]

avec R, processeur i7 - 2.6GHz

> ptm<-proc.time()
> for(x in 1:1000000)y<-x+8
> proc.time()-ptm
utilisateur système écoulé
0.060 0.008 7.890

le temps "système" (8ms) est le temps utilisé par le CPU alloué au processus appelant, le temps "utilisateur" (60ms) est le temps CPU alloué à l'utilisateur (en l'occurrence moi) qui a créé le processus. Le temps écoulé (un peu moins de 8 secondes) n'a pas de signification, il dépend de la vitesse avec laquelle j'ai tapé la troisième commande.

[invitebb943ab6]

Ok, j'ai aussi 32491 nombres...

C'est une erreur.
De même qu'ici :

Correction, je n'ai pas compté le nombre 100 000. Ça fait donc un de plus.

car 100000 a 5 chiffres 0, donc n'est pas solution.

de 1 à 100000, il y a 32490 nombres dont les chiffres sont tous différents.
Cf message #20 pour un algorithme un tantinet plus compact (2 lignes) que ceux déjà proposés...

[mp3dux]

@ID123 j'ai compté 0 moi donc on a 32490+1...
langage EEA c'est quoi ?

@minushabens
le temps d’exécution du cpu est donc lequel 8ms ?

[invite9dc7b526]

le temps à prendre en compte est 60ms. D'ailleurs si je remplace un million par un milliard j'ai un temps user de 66 secondes (1000 fois plus donc) mais le temps system ne change quasiment pas. Ca doit être le temps d'exécution de la fonction de mesure du temps (!) Enfin c'est ce que je devine.

[invitebb943ab6]

@ID123 j'ai compté 0 moi donc on a 32490+1...
l

pas recevable car

"Trouver tous les nombres composés de chiffres tous différents entre 1 et 100 000."

[Forthman]

je trouve également 32490 nombres avec des chiffres différents pour les nombres de 1 à 100000
Au début je n'en ai trouvé que 15120, mais c'est parce que je comptais les zéros à gauche donc "000001" était compté comme ayant 5 chiffres identiques...

[invitebb943ab6]

@ID123 langage EEA c'est quoi ?

C'est expérimental. Ca ressemble par certains côtés à l'APL, avec un traitement de listes et de foncteurs (=opérateurs d'opérateurs : les petits ° dans le programme), ce qui permet une très grande compacité d'écriture, ce qui se paye par une difficulté de lecture du code source.

[mp3dux]

je trouve également 32490 nombres avec des chiffres différents pour les nombres de 1 à 100000
Au début je n'en ai trouvé que 15120, mais c'est parce que je comptais les zéros à gauche donc "000001" était compté comme ayant 5 chiffres identiques...

combien de temps ? Et sur quoi comme machine ?

pas recevable car

en effet tu as raison, c'est comme ça qu'on sort d'un exam tout content et on se tape un 0, mon excuse ça fait un bail que je ne compte plus à partir de 1...
Ou d’ailleurs le prof doit annuler le sujet il a pas précisé que c'est en décimal on aurait cru du binaire, en plus il aurait dû préciser tous les nombres "entiers"

Du coup ça a tourné sur quoi comme machine ?

[Forthman]

Je l'ai écrit en Forth, (gforth) et ça prend un peu moins de 0.6 secondes sur mon eeepc1000h (atom N270 à 1.6GHz)

[invitebb943ab6]

Du coup ça a tourné sur quoi comme machine ?

Pas un foudre de guerre : un laptop i5-7300U @ 2.6 Ghz