Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
3063 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  complement a 8

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

complement a 8

n°1566022
neufcm
Posté le 28-05-2007 à 09:22:27  profilanswer
 

bonjour a tous
Dans le cadre d'un projet j'ai besoin d'un algo de complément a 8 je m'explique
 
je recupere une liste de client ayant chacun un certain nombre de dossiers associés (de 1 a 7 dossiers).  
 
exemple le client 90000 possede 3 dossiers
            le client 90001 possede 6 dossiers  
 
ainsi de suite  
 
je traite ces dossiers en les rengeants dans des emplacements contenant 8 places .Pour les traité je recupere une liste des clients triée par nombre de dossier donc du  plus grand au plus petit  
 
dans mon exemple donc le 90001 et ensuite le 90000
 
Je peux tres bien avoir dans un emplacement le 90000 de ranger il possede 3 dossier il reste donc 5 place (pour arriver aux 8 places par l'emplacement)
j'ai donc besoin d'un algo me permettant de faire le complément a 8 pour avoir des emplacement optimisé et rempli sachant que bien sur un client ne peut etre que dans un seul emplacement.  
 
Par exemple si un client possede 7 dossier il prendra un emplacement et il faudra trouver un client avec 1 seul dossier pour completer voir le laisser tel quel s'il n'y a pas de client avec 1 dossier
 
si quelqu'un peut m'aider sa serait super merci
bye a biento

mood
Publicité
Posté le 28-05-2007 à 09:22:27  profilanswer
 

n°1566037
phosphorel​oaded
Posté le 28-05-2007 à 10:12:36  profilanswer
 

A/ Disposer de la liste des clients ayant 8 dossiers, de ceux ayant 0 dossier puis 7 puis 1 puis 6 puis 2 ... (classé comme ça ou de 0 à 8 / 8 à 0 peu importe :)) Un hash (tableau à 9 entrées menant vers des listes chaînées) serait pas mal, ça dépend un peu de la nature de tes données au départ.

 

B/ A 8 et 0 dossiers c'est vite traité :D

 

C/ Avec "7 dossiers" tu ne peux que placer des "1 dossier". Tu regroupes autant de "1 dossier" que possible avec ceux-ci. S'il y a plus de 7 que de 1, rien à faire de mieux et il y aura de la place perdue.

 

D/ Avec "6", les "2" puis les "1" si possible.

 

E/ Avec "5" les 3 puis 2(+1)

 

F/ Avec "4", je sais pas ce qui est plus efficace entre les réunir par paires ou d'abord mettre les "1", "2", "3" restants. En fait il faut peut-être mettre les "1" puis les "2" aux étapes D et E? :??: Ca dépend peut-être aussi de la nature de tes données (ou pas), est-ce qu'il vaut mieux éviter d'avoir plusieurs "emplacements de 8 cases" pas remplis complètement (mais bien remplis à 6 ou 7 chacun) ou bien éviter au maximum tout trou dans ces emplacements? Dans ce dernier cas, à la fin ils doivent être tous remplis sauf éventuellement un qui sera Si ce qui est important est de minimiser le nombre d'emplacements pris alors le minimum théorique t'es connu: partie entière de la somme des dossiers divisée par 8 + 1 incomplet (dans lequel y a le reste de cette division par 8), m'enfin s'il y a que des "7" tu n'atteindras jamais ce minimum évidemment ;)


Message édité par phosphoreloaded le 28-05-2007 à 10:19:38
n°1566044
MagicBuzz
Posté le 28-05-2007 à 10:27:56  profilanswer
 

C'est un peu le problème de l'optimisation de l'espace sur un CD.
Il y a plusieurs topics à ce sujet. Effectivement, celui-ci est pas mal car très simple à mettre en oeuvre :)

n°1566049
neufcm
Posté le 28-05-2007 à 10:39:13  profilanswer
 

oui c'est un peu ce probleme en effet magicbuzz  
PhosphoRel oaded je dispose de la liste de mes clients avec pour chacun leur nombre de dossier et ils sont triés par nombre de dossier décroissant  
je suis ok avec toi je stocke toutes les combinaisons
je test quand je part de 6 si j'ai du 4 sinon je descend et ainsi de suite mais je voulais savoir si il y avait d'autres méthodes que stocké toutes les combinaisons dans un tableau et les essayé  
Pour le remplissage je doit avoir aucun trou dans chaque compartiment

n°1566359
MagicBuzz
Posté le 28-05-2007 à 19:55:31  profilanswer
 

Vu que je m'emmerdais beaucoup ce soir, je me suis amusé à adapter l'algo proposé par PhophoReloaded en T-SQL (SQL Server)
 

Code :
  1. CREATE TABLE cnt
  2. (
  3.  id tinyint NOT NULL PRIMARY KEY,
  4.  sz tinyint NOT NULL
  5. );
  6. go
  7. CREATE INDEX ix_cnt_sz ON cnt (sz);
  8. go
  9. CREATE FUNCTION show_cnt(@id AS tinyint)
  10. returns varchar(32)
  11. AS
  12. begin
  13.  declare @sz tinyint;
  14.  declare @ret varchar;
  15.  SELECT @sz = sz FROM cnt WHERE id = @id;
  16.  RETURN '[' + replicate('=', (@sz - 1) * 2) + cast(@id AS char(2)) + replicate('=', (@sz - 1) * 2) + ']';
  17. end;
  18. go
  19. CREATE FUNCTION order_cnt()
  20. returns @tmp TABLE
  21. (
  22.  id tinyint PRIMARY KEY NOT NULL,
  23.  sz tinyint NOT NULL,
  24.  ln tinyint NOT NULL
  25. )
  26. AS
  27. begin
  28.  INSERT @tmp
  29.  SELECT id, sz, 0
  30.  FROM cnt;
  31.  
  32.  declare @ln tinyint;
  33.  SET @ln = 1;
  34.  while EXISTS (SELECT NULL FROM @tmp WHERE ln = 0)
  35.  begin
  36.  UPDATE @tmp
  37.    SET ln = @ln
  38.    WHERE ln = 0
  39.    AND id = (SELECT top 1 id FROM @tmp WHERE ln = 0 ORDER BY sz DESC, id);
  40.  
  41.    while EXISTS (SELECT NULL FROM @tmp WHERE ln = 0 AND sz <= (8 - (SELECT sum(sz) FROM @tmp WHERE ln = @ln)))
  42.    begin
  43.      UPDATE @tmp
  44.      SET ln = @ln
  45.      WHERE ln = 0
  46.      AND id = (SELECT top 1 id FROM @tmp WHERE ln = 0 AND sz <= (8 - (SELECT sum(sz) FROM @tmp WHERE ln = @ln)) ORDER BY sz DESC, id);
  47.    end;
  48.    SET @ln = @ln + 1;
  49.  end;
  50.  RETURN;
  51. end;
  52. go
  53. CREATE FUNCTION display_ordered_cnt()
  54. returns @tmp TABLE
  55. (
  56.  dsp varchar(32)
  57. )
  58. AS
  59. begin
  60.  declare @cln tinyint;
  61.  declare @oln tinyint;
  62.  declare @dsp varchar(32);
  63.  declare @dln varchar(32);
  64.  
  65.  declare cur cursor LOCAL fast_forward
  66.  FOR
  67.  SELECT ln, dbo.show_cnt(id)
  68.  FROM order_cnt()
  69.  ORDER BY ln, id;
  70.  
  71.  open cur;
  72.  
  73.  fetch next FROM cur
  74.  INTO @cln, @dsp;
  75.  SET @dln = '';
  76.  SET @oln = @cln;
  77.  
  78.  while @@FETCH_STATUS = 0
  79.  begin
  80.    IF @oln <> @cln
  81.    begin
  82.      INSERT @tmp SELECT @dln;
  83.      SET @dln = '';
  84.      SET @oln = @cln;
  85.    end;
  86.    SELECT @dln = @dln + @dsp;
  87.    fetch next FROM cur
  88.    INTO @cln, @dsp;
  89.  end;
  90.  
  91.  IF @oln <> @cln
  92.  begin
  93.    INSERT @tmp SELECT @dln;
  94.  end;
  95.  
  96.  close cur;
  97.  
  98.  deallocate cur;
  99.  
  100.  RETURN;
  101. end;
  102. go
  103. print 'Initialisation de la table';
  104. declare @id AS tinyint;
  105. SET @id = 0
  106. while @id < 100
  107. begin
  108.  INSERT INTO cnt (id, sz) VALUES (@id, cast(rand() * 8 AS tinyint) + 1);
  109.  SELECT @id = @id + 1;
  110. end;
  111.  
  112. print 'Tests';
  113. SELECT * FROM display_ordered_cnt();


 
Et ça marche :bounce:
 


Initialisation de la table
 
(1 row(s) affected)
 
(1 row(s) affected)
 
[...]
 
(1 row(s) affected)
 
(1 row(s) affected)
Tests
dsp
--------------------------------
[==============3 ==============]
[==============10==============]
[==============18==============]
[==============19==============]
[==============25==============]
[==============60==============]
[==============73==============]
[==============76==============]
[==============79==============]
[==============82==============]
[==============85==============]
[==============91==============]
[0 ][============4 ============]
[2 ][============14============]
[6 ][============28============]
[30][============56============]
[38][============58============]
[45][============65============]
[63][============66============]
[============67============][68]
[============72============][81]
[94][============96============]
[============98============]
[==9 ==][==========13==========]
[==11==][==========27==========]
[==20==][==========31==========]
[==23==][==========33==========]
[==29==][==========46==========]
[==32==][==========47==========]
[==37==][==========51==========]
[==40==][==========55==========]
[==41==][==========57==========]
[==43==][==========61==========]
[==53==][==========83==========]
[==75==][==========89==========]
[==84==][==========92==========]
[========1 ========][====5 ====]
[====7 ====][========8 ========]
[========12========][====16====]
[====21====][========24========]
[====22====][========26========]
[========34========][====42====]
[========35========][====49====]
[========36========][====69====]
[========44========][====71====]
[========48========][====77====]
[========54========][====80====]
[========59========][====87====]
[========64========][====93====]
[========74========][====99====]
[========78========]
[========90========]
[========97========]
[======15======][======17======]
[======39======][======50======]
[======52======][======62======]
[======70======][======86======]
 
(57 row(s) affected)


Message édité par MagicBuzz le 28-05-2007 à 19:55:50
n°1566363
MagicBuzz
Posté le 28-05-2007 à 20:08:26  profilanswer
 

PS : Ceci dit, l'algo est améliorable. Il faudrait faire une seconde passe pour tenter de boucher mieux les trous.
 
Exemple :


id sz
-- --
 1  4
 2  3
 3  3
 4  2
 5  2
 6  2


 
L'algo donne :


[======1 ======][====2 ====] (1 place perdue)
[====3 ====][==4 ==][==5 ==] (1 place perdue)
[==6 ==]                     (6 places perdues)


=> 8 places perdues et 3 lignes
 
Alors qu'à la main, on arrive à ça :


[======1 ======][==4 ==][==5 ==] (0 place perdue)
[====2 ====][====3 ====][==6 ==] (0 place perdue)


=> 0 place perdue et 2 lignes

n°1568051
neufcm
Posté le 31-05-2007 à 15:39:02  profilanswer
 

c bon me suis debrouillé et je perd aucune place tant que c'est possible merci en tout cas de t'etre impliqué :-)


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  complement a 8

 

Sujets relatifs
Calcul complement à 2[Complément] Statistiques saison de hockey
[VB6] Pb avec le gestionnaire de complement sous VB6[java] convertir un Integer en binaire complément a 2 ?
Plus de sujets relatifs à : complement a 8


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR