[Problème] Où couper la chaine binaire?

Rappel du premier message :


PROBLEME
On vous donne une suite de '0' et de
'1'. Ecrire un programme qui détermine la position avant laquelle il
faut couper cette suite pour que le nombre de '1' à gauche de cette
coupure plus le nombre de '0' à droite soit le plus petit possible.

Les positions sont comptées à partir de 0. Pour couper tout à gauche, on coupe donc avant la position 0.

EXEMPLESi la chaine est:

001101011000010110110011101001101010101010
Alors la position à retourner est: 13

001101011000: nombre de 1 est 5

010110110011101001101010101010: nombre de 0 est 14
14 5=19 (le minimum)

nawel a écrit:merci nabil et manianis pour l'explication.je veux des autres exemples pour que j'habituer.

d'accord, c promis!

mosa a écrit:je suis pas habitué à ce genre de problème, pouvez-vous me proposer des exercices préliminaires concernant le calcul binaire?

Promis mosa
Je ferai le nécessaire prochainement.

MERCI NABIL. J'ATTENDS DES AUTRES EXERCICES ET JE VEUX AUSSI UNE APPLICATION AVEC COMPLEMENT A 1 ET COMPLEMENT A 2.

nawel a écrit:MERCI NABIL. J'ATTENDS DES AUTRES EXERCICES ET JE VEUX AUSSI UNE APPLICATION AVEC COMPLEMENT A 1 ET COMPLEMENT A 2.

Qu'est-ce que tu veux dire par COMPLEMENT A 1 ET COMPLEMENT A 2.

merci nabil de s'interesser par la proposition.
c le codage des entiers relatifs

kelk'1 peut m'expliquer comment on peut transformer l'entier 11 sur base décimale en 13 sur base octale et en 1011 sur base binaire, merci

mosa a écrit:kelk'1 peut m'expliquer comment on peut transformer l'entier 11 sur base décimale en 13 sur base octale et en 1011 sur base binaire, merci

Dans la base 10, le nombre 11 s'écrit:
1x10^1 + 1x10^0,
où a^b veut dire a puissance b.

Dans la base 8 (octal), le nombre 11 s'écrit:
1x8^1 + 3x8^0,
donc c'est égal à 13 dans la base (.

Dans la base 2 (binaire), le nombre 11 s'écrit:
1x2^3 + 0x2^2 + 1x2^1 + 1x2^0,
donc c'est égal à 1011 dans la base (2).

Faut pas oublier que:
Tout nombre entier a une unique écriture dans une base B donnée.

Nabil les nombres négatifs utilisent souvent une écriture en complément à 2.

Exemple :
5(10) = 101(2)
et
-5(10) = ? (2)

-->
Si l'entier est codé sur 8 bits on procède par une complémentation à 2 càd
1. on écrit 5 en base 2 : 0000 0101(2)
2. on fait une complémentation à 1 (0==>1 et 1==>0) : 1111 1010
3. on ajoute un au résultat : 1111 1010(2) + 1 = 1111 1011(2)
d'ou -5(10) = 1111 1011(2)

manianis a écrit:Nabil les nombres négatifs utilisent souvent une écriture en complément à 2.

Exemple :
5(10) = 101(2)
et
-5(10) = ? (2)

-->
Si l'entier est codé sur 8 bits on procède par une complémentation à 2 càd
1. on écrit 5 en base 2 : 0000 0101(2)
2. on fait une complémentation à 1 (0==>1 et 1==>0) : 1111 1010
3. on ajoute un au résultat : 1111 1010(2) + 1 = 1111 1011(2)
d'ou -5(10) = 1111 1011(2)

Merci de m'avoir rappeler ça manianis. Mais en général tant que l'énoncé n'a pas précisé ces détails, l'élève ne doit pas envisager toutes les hypothèses.
Mais tu as parfaitement raison.

oui c tt à fait manianis mé je veux des exercices pour tester mes connaissances puisque je l'étude cette semaine

merci Admin, et c'est à manianis de m'expliquer cé quoi les bits et de présenter un exemple

quelle est la règle à suivre pour transformer un entier négatif
d'une base décimal à une base octal et à une base binaire?

Il existe une méthode plus simple pour trouver la représentation d'un nombre négatif.

Rappelons que la représentation du nombre négatif dépend du nombre de bits utilisés pour le représenter.

bit = chiffre binaire (0 ou 1)

Si ce nombre de bits n = 8 et le nombre à représenter est a = -5.
rb = 2^n - 5 = 256 - 5 = 251
251(10) = 1111 1011(2)
251(10) = 373(
251(10) = FB(16)

on a oublié l'exercice posé ou quoi? j'ai fait un petit essai en version C++ que je vais poster

#include<stdio.h>
void main()

{int i,j,n,compt-0,compt_1,p,c,min,T,V;

printf("fixer la longueur de la chaîne");
scanf("%d",&n);

for (i=1;i<=n;i++)
{ while ((T[i]!=0) || (T[i]!=1))
{printf("T[%d]=",i);
scanf("%d",&T[i]);
}
}

compt_0=0; compt_1=0; p=2;
do
{for (i=1;i<=p-1;i++)
{ if (T[i]==1)
{compt_1++;}}

{for (j=n;j>=p+1;j--)
{ if (T[j]==0)
{compt_0++;}}

V[p-1]=compt_1+compt_0;
p=p+1;}
while(p<=n-1);

min=V[1];
for (i=1;i<=n-2;i++)
{ if (V[i]<min)
{min=V[i];
c=i;}}

printf("il faut couper la chaîne avant la %d ème position",i+2);
}

commentaire......

très bonne solution !!! bravo mosa.

est-ce que ça marche? je l'ai pas compilé car j'ai pas le logiciel C++.

mosa a écrit:est-ce que ça marche? je l'ai pas compilé car j'ai pas le logiciel C++.

mosa:
ton code source je viens de le compiler. Il a pas mal d'erreurs syntaxiques.
Il vaut mieux les corriger.

Essaie d'abord de bien définir l'algorithme puis on passera automatiquement à la programmation dans n'importe quel langage.

Tu peux télécharger DevC++ (compilateur + éditeur C/C++) il est gratuit!

Tu pourras aussi essayer codeblocks qui est meilleur.

http://www.codeblocks.org/

l'exercice est un peu compliqué je crois!
je l'ai trouvé dans un olympiade d'info! (en suisse)

petite rectification de l'énoncé :
PROBLEME
On vous donne une suite de '0' et de '1'. Ecrire un programme qui détermine la
position avant laquelle il faut couper cette suite pour que le nombre
de '1' à gauche de cette coupure plus le nombre de '0' à droite soit le plus
petit possible.
NB : Les positions sont comptées à partir de 0. Pour couper tout à
gauche, on coupe donc avant la position 0.
EXEMPLE Si la chaine est:
001101011000010110110011101001101010101010
Alors la position à retourner est: 13 {à partir de 0}
Donc on coupe avant cette position et on obtiendra :
0011010110000: nombre de 1 est 5
10110110011101001101010101010: nombre de 0 est 13
13 + 5=18 (le minimum)
{------------------------------------solution envisageable------------------------------------------------------------------}

Code:


program coupure;
uses wincrt;
procedure saisir(var seq : string);
{---------------------------------------------------}
function verif(ch:string):boolean;
var
i:integer; v:boolean;
begin
v:=true;
i:=0;
while(v) and (i<length(ch)) do
begin
    i:=i+1;
    if not(ch[i] in ['0','1']) then
    begin
    v:=false;
    end;
end;
verif:=v;
end;
{-------------------------------------------------}
begin
    repeat
    begin
    write('entrer la séquence binaire :');
    readln(seq);
    end
    until(verif(seq)) and (length(seq)>0);;
end;
{-------------------------------------------------}
function nbr_de_1(ch:string;p:integer):integer;
var
i,nb:integer;
begin
nb:=0;
if p<>1 then
  begin
        for i:=1 to p-1 do
        begin
            if (ch[i]='1') then
            begin
            nb:=nb+1;
            end;
        end;
  end;
nbr_de_1:= nb;
end;
{-------------------------------------}
function nbr_de_0(ch:string;p:integer):integer;
var
i,nb:integer;
begin
nb:=0;
        for i:=P to length(ch) do
            begin
            if (ch[i]='0') then
            begin
            nb:=nb+1;
            end;
        end;
nbr_de_0:=nb;
end;
{-------------------------------------}
function position(ch:string):integer;

var
m,p,i,x:integer;
begin
m:=length(ch);
p:=1;
for i:=1 to length(ch) do
begin
x:=nbr_de_1(ch,i)+nbr_de_0(ch,i);
{writeln('itération ',i,' x= ',x);}
    if (x<m) then
    begin
    m:=x;
    p:=i;
    end;
end;
position:=p;
end;
{-------------------------------------}
var
seq:string;
x:integer;
begin
saisir(seq);
x:= position(seq);
writeln('on coupe avant la position : ',x-1);
writeln(copy(seq,1,x-1),' : avec nombre de 1 = ',nbr_de_1(seq,x));
writeln(copy(seq,x,length(seq)-(x-1)),' : avec nombre de 0 = ',nbr_de_0(seq,x));
end.

{------------------------à vous lire--------------------------------------------------------------}

C'est très acceptable comme solution Bravo!

Mais juste quelques simples remarques: ces deux fonctions font presque la même chose !!!

Code:

function nbr_de_1(ch:string;p:integer):integer;
function nbr_de_0(ch:string;p:integer):integer;


ça sera plus intelligent de les réduire à une seule fonction:

Code:

function nbr_occurence(ch:string; deb:integer; fin:integer; motif:char):integer;

qui vérifie combien de fois le caractère "motif" est présent dans la chaine "ch" entre les positions "deb" et "fin".

On l'utilisera de deux manières:
function nbr_occurence(ch,1,p,'1')
function nbr_occurence(ch,p+1,length(ch),'0')

très pertinente comme remarque merci j'écrirai la version 1.1

methodiX a écrit:C'est très acceptable comme solution Bravo!

Mais juste quelques simples remarques: ces deux fonctions font presque la même chose !!!

Code:

function nbr_de_1(ch:string;p:integer):integer;
function nbr_de_0(ch:string;p:integer):integer;


ça sera plus intelligent de les réduire à une seule fonction:

Code:

function nbr_occurence(ch:string; deb:integer; fin:integer; motif:char):integer;

qui vérifie combien de fois le caractère "motif" est présent dans la chaine "ch" entre les positions "deb" et "fin".

On l'utilisera de deux manières:
function nbr_occurence(ch,1,p,'1')
function nbr_occurence(ch,p+1,length(ch),'0')

Toujours faire attention aux valeurs des paramètres de la fonction:
ch: ne doit pas être nulle, sinon return False.
deb: doit être entre 1 et length(ch)
fin: doit être entre deb+1 et length(ch)


Le danger de cette méthode c'est dans son utilisation. Elle doit comporter énormément de contrôle pour finir à être moins pratique que la proposition intiale.