Problema de división completa del número 200 (si hay solución, se sumarán hasta 200 puntos)
(1)
Para explicar este tema claramente de antemano, planeo usar una metáfora, y otra razón es que la información a la que hice referencia también usa esta metáfora para explicarlo. . de esta pregunta.
Entonces se puede pensar en colocar 200 manzanas en 25 platos.
Usamos f(m,n) para representar el número de formas de poner m manzanas en n platos (la diferencia es que el plato puede estar vacío, y cuando no puede estar vacío, solo necesitamos discutir Haga un pequeño cambio, que se discutirá más adelante). Ahora echemos un vistazo a un algoritmo recursivo:
Analicemos n primero. Si n>m, debe haber n-m placas que siempre estarán vacías.
El método. de colocar manzanas El número no tiene efecto; es decir,
if(n>m) f(m,n) = f(m,m)
Cuando n<=m , diferentes métodos de colocación Se puede dividir en dos categorías: es decir, al menos un
plato está vacío o todos los platos tienen manzanas. El primer caso es equivalente a
f(m. ,n) = f(m, n-1);
En este último caso se puede sacar una manzana de cada plato sin afectar
el número de colocaciones diferentes, es decir ,
f(m,n) = f(m-n,n) Y el número total de formas de poner manzanas es igual a la suma de las dos, es decir,
. f(m,n) =f(m,n-1)+f(m-n,n)
La salida de esta recursividad es:
Cuando n=1, todas las manzanas debe colocarse
En un plato, por lo que se devuelve 1; cuando no hay ninguna manzana para poner,
se define como 1 forma de ponerla en las dos formas recursivas; los primeros n se colocarán uno por uno
Disminuya gradualmente y eventualmente llegará a la salida n==1. El segundo m disminuirá gradualmente
Porque cuando n>m, tenemos devolverá f(m,m), por lo que eventualmente
Alcanzará la salida m==0.
Pero como no puede haber platos vacíos en el problema a resolver, primero se debe colocar una manzana en cada plato, por lo que la conclusión final es que sólo es necesario calcular el valor de f(175,25). calculado.
El algoritmo recursivo requerirá muchos cálculos al calcular manualmente números grandes. Si el programa está escrito en lenguaje C, el programa fuente es:
/** ****. ********************************/
//(Porque no hay ningún software de compilación instalado en la computadora, puede haber un ERROR)
#include
int f(int m, int n){
if(n ==1 || m==0) devuelve 1;
si(n>m) devuelve f(m,m);
devuelve f(m,n-1) +f( m-n,n);
}
void main(){
int re;
re=f(175 ,25) ;
printf("%d\n",re);
}
//Nota: descargar materiales de referencia/cpp2007/lecture/ 7.pdf
/************************************/
(2)
Este problema es un problema de combinación simple. Como se mencionó en el primer piso, simplemente inserte aleatoriamente 24 particiones en los 199 espacios entre las 200 manzanas.
El último paso es pedir C (199, 24)
/****************************** ******* */
//(Dado que no hay ningún software de compilación instalado en la computadora, puede haber un ERROR)
#include
int c(int m, int n){//El algoritmo de combinación es seleccionar aleatoriamente n de m
if(n==0 || n==m) return 1;
return c(m-1,n)+c(m-1,n-1);
}
void main(){
int re ;
re=c(199,24);
printf("%d\n",re);
}
/************************************/
(3)
Empieza colocando 4 en cada plato. Ahora solo quedan 100 manzanas y 25 platos, y puedes poner manzanas en cualquiera de los platos aquí, formando un modelo: 100 manzanas y 25 platos forman 125 posiciones, y los platos deben ocuparlas se requieren 25 posiciones C (125. ,25)
/************************************ ***** /
//(Dado que el software de compilación no está instalado en la computadora, puede haber ERROR)
#include
int c (int m, int n){//El algoritmo de combinación consiste en seleccionar aleatoriamente n de m
if(n==0 || n==m) return 1;
return c(m-1,n)+c(m-1,n-1);
}
void main(){
int re;
re=c(125,25);
printf("%d\n",re);
}
p>
/************************************/