Partage de technologie

Pratique quotidienne du concours préliminaire de l'Olympiade d'informatique-44-CSP-J2020 Questions de base - Permutation et combinaison, principe de multiplication, méthode de regroupement, méthode de partition, exemples et applications de méthode d'élimination

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Mot-clé de réponse au compte public du document PDF : 20240711
Insérer la description de l'image ici

Questions à choix multiples du CSP-J 2020

Questions à choix multiples (15 questions au total, 2 points chacune, 30 points au total : chaque question a une et une seule bonne option)

10. Il y a 5 enfants alignés côte à côte. Deux des enfants sont des jumeaux. Si les deux jumeaux doivent être adjacents, y a-t-il ( ) différentes manières de les disposer ?

A.48

B.36

C.24

D.72

13. La chronologie des tiges et des branches est une méthode chronologique traditionnelle chinoise, qui consiste en 10 tiges célestes et 12 branches terrestres pour former 60 tiges célestes et branches terrestres. Les tiges célestes et branches terrestres correspondantes peuvent être calculées à partir de l'année civile grégorienne selon les formules et tableaux suivants.
Tiges célestes = le reste obtenu en divisant (année civile grégorienne) par 10
Branches terrestres = Reste de (année civile grégorienne) divisé par 12

Par exemple, cette année est 2020. Lorsque 2020 est divisé par 10, le reste est 0 et la table de recherche est « 庚 » ; lorsque 2020 est divisé par 12, le reste est 4 et la table de recherche est « Zi », donc cette année est l'année de Gengzi.
Qu'étaient les tiges célestes et les branches terrestres en 1949 ( )

A. Jiyou

B. Jihai

C. Ji Chou

D. Ji Mao

14. Il y a 10 quotas de trois bons élèves répartis dans 7 classes. Chaque classe a au moins un quota. Il existe ( ) différents plans d'allocation.

A.84

B.72

C.56

D.504

15. Il y a cinq paires de gants de couleurs différentes (un total de 10 gants, un pour chaque main gauche et une pour chaque main droite), et 6 gants en sont retirés en même temps. Existe-t-il des ( ) façons de fabriquer deux paires de gants. ?

A.120

B.180

C.150

D.30

2 points de connaissances associés

1) Principe de multiplication

Pour faire une chose, il faut la diviser en n étapes pour la réaliser. Il existe m1 façons différentes de faire la première étape, m2 façons différentes de faire la deuxième étape,..., il existe plusieurs façons différentes de faire la nième étape. étape.

Ensuite, il existe N=m1 * m2 * m3 ...* mn différentes manières de résoudre ce problème.

Chaque étape n’accomplit pas une chose, elle complète simplement une des étapes

Par exemple

Un clown de cirque a trois chapeaux, rouge, jaune et bleu, et deux paires de chaussures noires et blanches. Il porte un chapeau et une paire de chaussures à chaque fois qu'il se produit. Question : Combien de combinaisons différentes de chapeaux et de chaussures de clown existe-t-il ?

analyser

Il y a 2 étapes requises pour s'habiller avant une représentation

Étape 1 : Choisissez un chapeau, il y a 3 façons de le choisir

Étape 2 : Choisissez une paire de chaussures. Il existe deux façons de choisir.

Convient au principe de multiplication en 2 étapes, avec un total de 3 * 2 = 6 combinaisons

2) Méthode de regroupement

Les problèmes de contiguïté en matière de permutation et de combinaison peuvent être résolus par la méthode de regroupement.

L'idée de base de cette méthode est de traiter les éléments adjacents dans leur ensemble (c'est-à-dire un « gros élément ») puis de les organiser avec d'autres éléments.Dans le même temps, il faut faire attention à la disposition des éléments internes de ce « grand élément »

Les étapes spécifiques sont les suivantes :

Regroupez les éléments adjacents et traitez-les dans leur ensemble.

Disposez ce tout avec d'autres éléments.

Considérez la disposition des éléments au sein de cet ensemble.Puisqu’ils sont adjacents, l’ordre relatif entre eux doit être pris en compte

Exemple 1

5 garçons et 3 filles s'alignent. 3 filles doivent s'aligner ensemble. Combien y a-t-il de manières différentes ?

A. 240 B. 320 C. 450 D. 4320

Réponse D

analyser

Les 3 filles doivent être ensemble. Utilisez la méthode de regroupement pour regrouper les 3 filles en un seul élément.

étape 1

Traitez 3 filles comme un seul élément et disposez-les avec 5 garçons, un total de A(6,6)=6 * 5 * 4 * 3 *2 * 1=720

Étape 2

Disposez les trois filles en interne, A(3,3) = 3 * 2 * 1=6

Cela nécessite 2 étapes et le principe de multiplication doit être utilisé pour multiplier les nombres de permutation en 2 étapes : 720 * 6 = 4320 types.

2) Méthode de partition

Le problème de diviser n éléments identiques en m objets différents nécessite que tous les éléments soient divisés et que chaque objet soit divisé en au moins un élément.

Insérez m-1 planches dans n-1 espaces entre n éléments pour diviser n éléments en m groupes.

Il existe des types C(n-1,m-1) au total

n-1 signifie qu'il y a n-1 espaces entre n éléments, m-1 signifie que m-1 cartes peuvent être divisées en m groupes

exemple

Il y a 7 pommes de même taille. Elles doivent être réparties entre 3 enfants. Chaque enfant doit recevoir au moins 1 pomme. Combien y a-t-il de façons de diviser les pommes ?

analyser

7 pommes identiques doivent être distribuées à 3 enfants, c'est-à-dire que 7 pommes identiques sont réparties en 3 groupes, et 2 cloisons peuvent être insérées dans les 6 trous formés par les 7 pommes.

C(6,2)=6 * 5 /(2 * 1) = 15 sortes

Exclusion

Lorsque les situations qualificatives sont complexes et que les situations qualificatives sont uniques, il convient de soustraire les situations disqualifiantes de l’ensemble des situations.

exemple

Sur 6 garçons et 5 filles, 4 sont sélectionnés au hasard pour participer au concours. Il est nécessaire qu'au moins un garçon et une fille soient sélectionnés. Combien y a-t-il de méthodes de sélection différentes ?

A.240 B.310 C.720 D.1080

analyser

Le contraire d'avoir au moins un homme et une femme chacun est de sélectionner respectivement uniquement des garçons ou des filles, afin que cela puisse être modifié en C(11,4)-C(6,4)-C(5,4)=310.

3 Analyse des idées

10. Il y a 5 enfants côte à côte en ligne. Deux des enfants sont des jumeaux. Si les deux jumeaux doivent être adjacents, y a-t-il (A) différentes manières de les disposer ?

A.48

B.36

C.24

D.72

analyser

étape 1

Les jumeaux doivent être adjacents. Pour utiliser la méthode de regroupement, les jumeaux doivent être regroupés en un seul, puis disposés et combinés avec les trois autres.

A(4,4)

Étape 2

Il y a un ordre au sein des jumeaux, A est à gauche, B est à droite ou A est à droite et B est à gauche

Un(2,2)

D'après le principe de multiplication A(4,4) * A(2,2) = 4 * 3 * 2 * 1 * 2 *1 = 48

13. La chronologie des tiges et des branches est une méthode chronologique traditionnelle chinoise, qui consiste en 10 tiges célestes et 12 branches terrestres pour former 60 tiges célestes et branches terrestres. Les tiges célestes et branches terrestres correspondantes peuvent être calculées à partir de l'année civile grégorienne selon les formules et tableaux suivants.
Tiges célestes = le reste obtenu en divisant (année civile grégorienne) par 10
Branches terrestres = Reste de (année civile grégorienne) divisé par 12

Par exemple, cette année est 2020. Lorsque 2020 est divisé par 10, le reste est 0 et la table de recherche est « 庚 » ; lorsque 2020 est divisé par 12, le reste est 4 et la table de recherche est « Zi », donc cette année est l'année de Gengzi.
Que sont les tiges célestes et les branches terrestres en 1949 (C)

A. Jiyou

B. Jihai

C. Ji Chou

D. Ji Mao

analyser

Tige céleste : 1949%10 = 9 correspond à vous-même

Branches terrestres : 1949%12 = 5 correspond à Chou

Ainsi, les tiges célestes et les branches terrestres en 1949 étaient Ji Chou

14. Il y a 10 quotas de trois bons élèves répartis dans 7 classes. Chaque classe a au moins un quota. Il existe (A) différents plans d'allocation.

A.84

B.72

C.56

D.504

analyser

Le même quota est alloué à différentes classes. Chaque classe a au moins un quota, elle est divisée en 7 classes et 7 groupes sont requis.

6 cloisons peuvent être placées sur 9 étages

C(9,6)=C(9,3)=9 * 8 * 7 /(3 * 2 * 1) = 84

15. Il y a cinq paires de gants de couleurs différentes (un total de 10 gants, un pour chaque main gauche et une pour chaque main droite), et 6 gants en sont retirés en même temps. Existe-t-il (A) différentes façons de fabriquer deux paires. des gants ?

A.120

B.180

C.150

D.30

analyser

étape 1

Choisissez 2 paires de gants parmi 5 couleurs différentes

C(5,2)=5*4 /2=10

Étape 2

Vous devez choisir 6 gants, et il en reste 2. Choisissez-en 2 parmi les 6 gants restants.

C(6,2)=6 * 5 /2 =15

Puisque 2 paires de gants ont été sélectionnées à l'étape 1, vous ne pouvez pas sélectionner 1 paire à cette étape, sauf dans le cas d'1 paire. Il y a 3 situations au total.

15-3=12

Selon le principe de multiplication 10 * 12 = 120