Hola!! estoy iniciando un curso de C++ y me han mandado una serie de ejercicios. Con el siguiente, que os muestro, mehe clavado porque no tengo ningún ejemplo a seguir.
Me podrías decir como hacer el algoritmo?
En una cinta tenemos una secuencia Xn Xn-1 ... X1 X0 -1 de ceros y unos acabada por -1. Esta secuencia es la representación binaria del número
Xn2n + Xn-12n-1 + ... + X1*2 + x0
Diseñar un algorismo que calcule el numero representado sin utilizar vectores
Muchas gracias!!!
pues nose, simplemente me han dado este problema y me han dicho que diseñe el algoritmo.
No soy nada experta en este tema y no tengo ni idea de por donde empezar .
¿Sin utilizar vectores? ¿Cómo representas la cinta sin utilizar vectores? :\
Así a botepronto si he entendido bien lo que preguntas se me ocurre este pseudocódigo...
función binario_a_decimal (cinta)
inicio
entero i=0,j=0,resultado=0
mientras(posicion(cinta) distinto de -1)
inicio
avanzar(cinta)
j++
fin
mientras(j distinto de 0)
inicio
si(posicion(cinta) igual a 1)
inicio
resultado=resultado+(2^i)
fin
retroceder(cinta)
i++
j--
fin
devolver resultado
fin
Así muy a botepronto y sin pensar mucho, mira a ver si te sirve para hacerte una idea. Obviamente las operaciones sobre la cinta se definen según la implementación que hagas de la misma.
Si lo he entendido bien y es simplemente convertir un número binario a un número decimal el problema no es tan difícil. El hecho de no poder usar vectores supongo que indica que la intención del ejercicio es que realices el cálculo según vas viendo dígitos del número en binario (1 por 1) y no hagas cosas como primero leer la cinta y almacenarla en un vector para después hacer cálculos sobre eso.
El método para hacer la conversión leyendo dígito a dígito (imagínate que estás leyendo un dígito cada vez de un fichero o similar) depende de como supongas que se realiza la lectura de la cinta. Es decir, si empiezas por el bit menos significativo (X0) y vas avanzando o si empiezas por el bit más significativo (Xn).En cualquiera de los 2 casos no es necesario retrodecer la cinta y el cálculo se puede realizar en una "pasada".
Para el primer caso (empezar por X0 y seguir por X1,X2,...) el algoritmo es el típico:
int decimal=0;
int potencia=1;
while(actual(cinta) != -1){
decimal+=actual(cinta)potencia;
potencia=potencia2;
avanzar(cinta)
};
Para el segundo caso(empezar por Xn y seguir por Xn-1,Xn-2...) lo único que tienes que saber es qué le ocurre a un número binario cuando se le añade un dígito por la derecha:
-Si el dígito es 0: el número se multiplica por 2. Por ejemplo si tenemos el número binario 101 (5 decimal) y leemos un 0 quedaría el número 1010 (10 decimal).
-Si el digito es 1:el número se multiplica por 2 y se le suma 1. Por ejemplo si tenemos el número binario 101(5 decimal) y leemos un 1 quedaría el número 1011 (11 decimal).
Con esto es fácil darse cuenta de que el algoritmo es algo como:
int decimal=0;
while(actual(cinta) != -1){
decimal=decimal*2+actual(cinta);
avanzar(cinta);
};
Como dijo #4 luego la implementación real depende de como implementes la cinta, pero estos algoritmos son genéricos y podrás adaptarlos sea cual sea esa implementación.
#1 creo que la solución es tan sencilla como recorrer el número que te dan (dice cinta, pero será una cadena de caracteres o un numero 110011110011) digito por digito, y pasarlo a decimal supongo. Cada digito que pases lo tienes que multiplicar por 2 elevado a X donde X aumentará cada iteración en 1. (suponiendo que recorras el numero de derecha e izquierda)
Si ya lo pone, aunque raro, pero simplemente es pasar un número binario acabado en -1
01010101010-1
A decimal.
Es trivial.
El número se pasa de binario a decimal con:
sumatorio para toda pos de: 2pos * dígito[pos]
Pues ya lo tenemos, aunque al ir de delante hasta el final hay que retocarlo un poco ya que no sabes que posición ocupa el primer dígito que te den, pero si lo puedes multiplicar por dos y es lo mismo:
Voy a suponer que vamos leyendo la cinta haciendo elemento := leer; pero si puedes acceder a la lista directamente es lo mismo que hacer cinta[ i] o algo así.
res = 0;
elemento := leer();
mientras elemento != -1 hacer
res = res*2; + elemento;
elemento := leer();
fmientras
retorna res;
Veo que #5 da la sintaxis más correcta al poner "avanzarCinta()" en vez de leer, pero bueno, la idea es esta.
El programa se hace con 4 lineas igualmente, solo faltaría saber como acceder a los elementos de la cinta (yo he puesto leer, también se podría poner cinta[posición] o como han puesto arriba cosas como avanzarCinta() pero esto son tonterías del problema, nada importante)
sin utilizar vectores es usando modulo 10 y dividir entre 10 
esa es la pista 
puesto que lo que te dan es un entero, no un vector (string) o array de char
una vez que el chico sabe lo que tiene que hacer que es pasar un nº binario a decimal supongo que le costara poco trabajo realizar el algortimo, supongo que lo que no entenderia es el enunciado.
#8 más o menos. le vale con
digito = numero%10;
numero=numero/10;
Estaba pensando que % es el resto de la división, pero realmente también es el módulo,así que tienes razón y he dicho posiblemente lo que estabas pensando.
Es lo que te han dicho por ahi arriba, multiplicar por 2 (desplazar hacia la izquierda) y sumar 1 (en su caso).
Segun pone el enunciado, la secuencia va de Xn a X0 y finalizada en -1. Es decir tienes que ir en ese orden y en secuencia (uno detras de otro sin saltar). Los vectores no son secuenciales aunque se recorran mucho en secuencial.
#8 , #10 Son numeros binarios a decimales, no hacen falta esas cosas.
#11 Dependerá de si la "cinta" que le pasan, es un string, un entero, un array...
visto que termina en -1 un entero no puede ser, así que lo que había dicho no podía ser.
¿ Y porque no iban a ser enteros ? ¿ Una lista de enteros ? Una cinta secuencial yo lo consideraria algo asi :
objetos:
cinta.situarseAlInicio()
cinta.siguiente()
estructurado:
situarseAlInicio(&cinta);
elemento = siguiente(&cinta); ó
siguiente(&cinta,&elemento);
La cinta puede ser de cualquier tipo de elemento, asi que si, pueden ser enteros, caracteres no porque hay un -1, a no ser que sean caracteres con signo, y tendrias el -1.
Entero != Natural, que he dudado ahora por un momento y igual te has liado tu tambien.