Temat: Analiza ciągów, systemy liczbowe. Temat: Analiza ciągów, systemy liczbowe Ile jest ciągów znaków o długości 6?
32) Ile różnych ciągów znaków o długości 3 istnieje w czteroliterowym alfabecie (A, B, C, D), jeśli wiadomo, że jednym z sąsiadów A jest koniecznie D, a litery B i C są nigdy obok siebie?
33) Wszystkie 5-literowe słowa składające się z liter P, O, R, T są pisane w kolejności alfabetycznej i numerowane. Oto początek listy:
Ile słów znajduje się pomiędzy słowami AX i ROMOR (łącznie z tymi słowami)?
40) Alexey kompiluje tabelę słów kodowych do przesyłania wiadomości; każda wiadomość ma swoje własne słowo kodowe. Jako słowa kodowe Aleksiej używa 5-literowych słów, które zawierają tylko litery A, B, C, X, przy czym litera X może pojawić się na ostatnim miejscu lub nie pojawić się wcale. Ilu różnych słów kodowych może użyć Alexey?
51) Vasya tworzy 5-literowe słowa, które zawierają tylko litery K, A, T, E, P, a litera P występuje w każdym słowie co najmniej 2 razy. Każda z pozostałych prawidłowych liter może pojawić się w słowie dowolną liczbę razy lub wcale. Słowo to dowolny prawidłowy ciąg liter, niekoniecznie znaczący. Ile słów może napisać Wasia?
53) Vasya tworzy 5-literowe słowa, które zawierają tylko litery M, U, X, A, a litery U można użyć nie więcej niż 3 razy. Każda z pozostałych prawidłowych liter może pojawić się w słowie dowolną liczbę razy lub wcale. Słowo to dowolny prawidłowy ciąg liter, niekoniecznie znaczący. Ile słów może napisać Wasia?
55) Vasya tworzy 6-literowe słowa, które zawierają tylko litery Zh, I, R, A, F, a litera A jest używana w każdym słowie, ale nie więcej niż 4 razy. Każda z pozostałych prawidłowych liter może pojawić się w słowie dowolną liczbę razy lub wcale. Słowo to dowolny prawidłowy ciąg liter, niekoniecznie znaczący. Ile słów może napisać Wasia?
57) Vasya tworzy 6-literowe słowa, w których są tylko litery P, I, R, O, G, a każde słowo ma jedną literę P, a po niej musi znajdować się samogłoska. Każda z pozostałych prawidłowych liter może pojawić się w słowie dowolną liczbę razy lub wcale. Słowo to dowolny prawidłowy ciąg liter, niekoniecznie znaczący. Ile słów może napisać Wasia?
59) Vasya tworzy 5-literowe słowa, które zawierają tylko litery P, I, R, O, G, a w każdym słowie litera P może wystąpić nie więcej niż dwa razy, a jeśli istnieje, to musi po niej nastąpić litera samogłoskowa. Każda z pozostałych prawidłowych liter może pojawić się w słowie dowolną liczbę razy lub wcale. Słowo to dowolny prawidłowy ciąg liter, niekoniecznie znaczący. Ile słów może napisać Wasia?
61) Iwan tworzy 5-literowe słowa z liter A, B, C, D, D, E, Yu, Z. Pierwszą i ostatnią literą tego słowa mogą być tylko litery E, Yu lub Z; występować na innych stanowiskach. Ile różnych słów kodowych może utworzyć Iwan?
67) Palindrom to ciąg znaków, który brzmi tak samo w obu kierunkach. Ile różnych 6-znakowych palindromów można utworzyć z małych liter łacińskich? (Alfabet łaciński ma 26 liter).
Temat: Analiza ciągów, systemy liczbowe.
Co musisz wiedzieć:
· zasady pracy z liczbami zapisanymi w systemach liczb pozycyjnych
Przykładowe zadanie:
Ile różnych ciągów znaków o długości 5 istnieje w czteroliterowym alfabecie (A, C, G, T), które zawierają dokładnie dwie litery A?
Rozwiązanie:
1) rozważyć różne opcje Słowa składające się z 5 liter, które zawierają dwie litery A i zaczynają się na A:
AA*** A*A** A**A* A***A
Tutaj gwiazdka oznacza dowolny znak ze zbioru (C, G, T), czyli jeden z trzech znaków.
2) zatem w każdym szablonie znajdują się 3 pozycje, z których każdą można wypełnić na trzy sposoby, tzw całkowita liczba kombinacji (dla każdego wzoru!) wynosi 33 = 27
3) są tylko 4 wzory, dają 4 27 = 108 kombinacji
4) teraz rozważamy wzorce, w których pierwsza litera A znajduje się na drugiej pozycji, są tylko trzy z nich:
*AA** *A*A* *A**A
dają 3 27 = 81 kombinacji
5) dwa wzory, gdzie pierwsza litera A znajduje się na trzeciej pozycji:
dają 2 27 = 54 kombinacje
6) i jeden wzór, w którym na końcu pojawia się kombinacja AA
dają 27 kombinacji
7) w sumie otrzymujemy (4 + 3 + 2 + 1) · 27 = 270 kombinacji
8) odpowiedź: 270.
Inne przykładowe zadanie:
Ile słów o długości 5, zaczynających się od samogłoski, można ułożyć z liter E, G, E? Każda litera może wystąpić w słowie kilka razy. Słowa nie muszą być znaczącymi słowami w języku rosyjskim.
Rozwiązanie:
1) pierwszą literę słowa można wybrać na dwa sposoby (E lub E), resztę - na trzy sposoby
2) całkowita liczba różnych słów wynosi 2*3*3*3*3 = 162
3) odpowiedź: 162.
Rozwiązanie (poprzez wzory):
1) Biorąc pod uwagę słowo o długości 5 znaków, np. *****, gdzie czerwona gwiazdka to litera samogłoskowa (E lub E), a czarna litera to dowolna z trzech podanych.
2) Ogólny wzór na liczbę opcji:
N = M L, Gdzie M jest potęgą alfabetu, oraz L– długość kodu.
3) Ponieważ położenie jednej z liter jest ściśle regulowane (znak mnożenia w zdarzeniach zależnych), wzór na wszystkie opcje będzie miał postać: N=M 1L 1∙ M 2L2 ,
4) Następnie M 1 = 2 (alfabet liter samogłoskowych) i L 1 = 1 (tylko 1 pozycja na słowo).
M 2 = 3 (alfabet wszystkich liter) i L 2 = 4 (pozostałe 4 pozycje w słowie).
5) W rezultacie otrzymujemy: N= 21 ∙ 34 = 2 ∙ 81 = 162.
6) odpowiedź: 162.
Inne przykładowe zadanie:
Wszystkie 4-literowe słowa składające się z liter K, L, R, T są zapisywane w kolejności alfabetycznej i ponumerowane. Oto początek listy:
1. KKKK
2. KKKL
3.KKKR
4. CCCP
Zapisz słowo, które znajduje się na 67. miejscu od początku listy.
Rozwiązanie:
1) najprostszą opcją rozwiązania tego problemu jest użycie systemów liczbowych; Rzeczywiście, tutaj układ słów w porządku alfabetycznym jest równoważny uporządkowaniu w porządku rosnącym liczb zapisanych w czwartorzędowym systemie liczbowym (podstawa systemu liczbowego jest równa liczbie użytych liter)
2) zastąpimy K®0, L®1, R®2, T®3; ponieważ numeracja słów zaczyna się od jedynki, a pierwszą liczbą ККК®0000 jest 0, liczba 67 będzie liczbą 66, którą należy przeliczyć do systemu czwartorzędowego: 66 = 10024
3) Po dokonaniu zamiany odwrotnej (cyfry z literami) otrzymujemy słowo LKKR.
4) Odpowiedź: LKKR.
Inne przykładowe zadanie:
Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej.
Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Rozwiązanie (metoda 1, zaczynając od końca):
5) policz, ile pięcioliterowych słów można ułożyć z trzech liter;
6) oczywiste jest, że są tylko 3 jednoliterowe słowa (A, O, U); dwuliterowe słowa to już 3'3=9 (AA, AO, AU, OA, OO, OU, UA, OU i OU)
7) podobnie można wykazać, że jest tylko 35 = 243 słów składających się z 5 liter
8) oczywiste jest, że ostatnie, 243. słowo to UUUUU
10) Odpowiedź: UUUUU.
2) wpisz początek listy, zastępując litery cyframi:
1. 00000
2. 00001
3. 00002
4. 00010
6) zamień cyfry z powrotem na litery: 22212 ® УУУУУ
7) Odpowiedź: UUUUU.
Rozwiązanie (trzecia metoda, wzory naprzemiennie):
1) policz, ile 5-literowych słów można utworzyć z trzech liter:
35 = 243 słowa; 240. miejsce – czwarte od końca;
2) ponieważ słowa są ułożone alfabetycznie, pierwsza tercja (81 sztuk) zaczyna się na „A”, druga tercja (również 81) na „O”, a ostatnia tercja na „U”, czyli pierwszą literę zmienia się w 81 słowach
3) podobne:
Druga litera zmienia się po 81/3 = 27 słów;
3. litera – po 27/3 = 9 słów;
4. litera – po 9/3 = 3 słowa i
Piąta litera zmienia się w każdym wierszu.
4) z tego wzoru jasno wynika, że
· na pierwszej pozycji szukanego słowa pojawi się litera „U” (ostatnie 81 liter);
· na drugiej – także litera „U” (ostatnie 27 liter);
· na trzeciej – także litera „U” (9 ostatnich liter);
· na czwartym – litera „O” (ponieważ trzy ostatnie litery to „U”, a przed nimi są 3 litery „O”)%
· na piątej – litera „U” (ponieważ 3 ostatnie litery występują naprzemiennie „A”, „O”, „U”, a przed nimi ta sama sekwencja).
5) Odpowiedź: UUUUU.
Inny przykład zadania (autor –):
Wszystkie 5-literowe słowa składające się z 5 liter A, K, L, O, Sh są pisane w kolejności alfabetycznej.
Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAL
4. AAAAA
5. AAAAA
6 . AAAAA
Gdzie jest słowo SZKOŁA z początku listy?
Rozwiązanie:
1) analogicznie do poprzedniego rozwiązania zastosujemy pięcioarniowy system liczbowy z zamianą A ® 0, K ® 1, L ® 2, O ® 3 i Ш ® 4
2) słowo SZKOŁA zostanie zapisane w nowym kodzie w następujący sposób: 413205
3) przekonwertuj tę liczbę na system dziesiętny:
413205 = 4×54 + 1×53 + 3×52 + 2×51 = 2710
4) ponieważ numeracja elementów listy zaczyna się od 1, a liczby w systemie pięcioarniowym zaczynają się od zera, to do otrzymanego wyniku należy dodać 1, to...
5) Odpowiedź: 2711.
Inne przykładowe zadanie:
Zapisane są wszystkie pięcioliterowe słowa składające się z liter A, O, U odwracać kolejność alfabetyczna. Oto początek listy:
1. UUUUUU
2. UUUUO
3. UUUUUA
4. UUUUUU
Zapisz słowo, które znajduje się na 240. miejscu od początku listy.
Rozwiązanie (druga metoda, system trójskładnikowy, pomysł M. Gustokashina):
1) zgodnie z warunkami zadania ważne jest jedynie użycie zestawu trzech różnych symboli, dla których określona jest kolejność (alfabetyczna); dlatego do obliczeń można użyć dowolnych trzech znaków, na przykład cyfr 0, 1 i 2 (dla nich kolejność jest oczywista - rosnąca)
2) wpisz początek listy, zastępując litery cyframi, tak aby kolejność znaków została odwrócona alfabetycznie(U → 0, O → 1, A → 2):
1. 00000
2. 00001
3. 00002
4. 00010
3) przypomina to (właściwie tak!) liczby zapisane w trójskładnikowym systemie liczbowym w kolejności rosnącej: liczba 0 jest na pierwszym miejscu, 1 jest na drugim miejscu itd.
4) wtedy łatwo zrozumieć, że 240. miejsce to liczba 239 zapisana w systemie liczb trójskładnikowych
5) przekonwertuj 239 na system trójskładnikowy: 239 = 222123
6) zamień cyfry z powrotem na litery, podany w odwrotnej kolejności alfabetycznej(0 → U, 1 → O, 2 → A): 22212 ® ААААА
7) Odpowiedź: AAAAA.
Cele szkolenia:
1) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Zapisz słowo, które znajduje się na 101. miejscu od początku listy.
2) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Zapisz słowo, które znajduje się na 125. miejscu od początku listy.
3) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Zapisz słowo, które znajduje się na 170. miejscu od początku listy.
4) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Zapisz słowo, które znajduje się na 210 miejscu od początku listy.
5) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5 . AAAAA
Zapisz słowo, które znajduje się na 150. miejscu od początku listy.
6) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5 . AAAAA
Zapisz słowo, które znajduje się na 250 miejscu od początku listy.
7) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5 . AAAAA
Zapisz słowo, które znajduje się na 350. miejscu od początku listy.
8) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5 . AAAAA
Zapisz słowo, które znajduje się na 450. miejscu od początku listy.
9) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
10) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
11) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Podaj numer słowa UAUAU.
12) Wszystkie 5-literowe słowa składające się z liter A, O, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAA
3. AAAAA
4. AAAAA
Wprowadź numer pierwszego słowa rozpoczynającego się na literę O.
13) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5. AAAKA
Wskaż numer pierwszego słowa rozpoczynającego się na literę U.
14) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5. AAAKA
Wskaż numer pierwszego słowa rozpoczynającego się na literę K.
15) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5. AAAKA
Podaj numer słowa RUKAA.
16) Wszystkie 5-literowe słowa składające się z liter A, K, R, U są pisane w kolejności alfabetycznej. Oto początek listy:
1.AAAAAA
2. AAAAK
3. AAAAR
4. AAAAA
5. AAAKA
Podaj numer słowa UKARA.
17) Wszystkie 5-literowe słowa składające się z liter K, O, P są pisane w kolejności alfabetycznej i numerowane. Oto początek listy:
1. KKKKK
2. KKKKO
3.KKKKR
4. KKKOK
238 .
18) Wszystkie 5-literowe słowa składające się z liter I, O, U są pisane w kolejności alfabetycznej i numerowane. Oto początek listy:
1.IIIIII
2.III
3. IIIU
4. IIIIOI
Zapisz słowo pojawiające się pod liczbą 240 .
19) Wszystkie 4-literowe słowa składające się z liter M, A, R, T są pisane w kolejności alfabetycznej. Oto początek listy:
1. AAAA
2. AAAAM
3. AAAR
4. AAAA
Zapisz słowo, które się powtarza 250 - miejsce od początku listy.
20) Wszystkie 5-literowe słowa składające się z liter P, O, K są pisane w kolejności alfabetycznej i ponumerowane. Oto początek listy:
1. KKKKK
2. KKKKO
3.KKKKR
4. KKKOK
Zapisz słowo pojawiające się pod liczbą 182 .
21) Ile słów o długości 4, zaczynających się od spółgłoski, można ułożyć z liter L, E, T, O? Każda litera może wystąpić w słowie kilka razy. Słowa nie muszą być znaczącymi słowami w języku rosyjskim.
22) Ile różnych ciągów znaków o długości 5 istnieje w trzyliterowym alfabecie (K, O, T), które zawierają dokładnie dwie litery O?
23) Ile różnych ciągów znaków o długości 6 istnieje w trzyliterowym alfabecie (K, O, T), które zawierają dokładnie dwie litery K?
24) Ile różnych ciągów znaków o długości 6 istnieje w czteroliterowym alfabecie (M, A, P, T), które zawierają dokładnie dwie litery P?
Źródła zadań:
1. Praca szkoleniowa MIOO 2011-2012.
Ile różnych ciągów znaków o długości 6 istnieje w czteroliterowym alfabecie, które zawierają dokładnie dwie identyczne litery?
Odpowiedzi:
zero, ponieważ jeśli poprawisz dwie identyczne litery, reszta musi być inna. okazuje się, że na pozycji 4 zostały już tylko 3 litery, co jest niewystarczające
Podobne pytania
- 7 klasa PROSZĘ!! 1. Skrzynia z ładunkiem o objętości 1,6 m(3) jest do połowy zanurzona w wodzie morskiej. Jaka siła Archimedesa na niego działa? 2. Ciężar kry wynosi 22,5 kN. Kry lodowa zanurzona jest w wodzie morskiej na głębokości 2,27 m (3). Jaki jest ciężar osoby na krze lodowej? 3. Do naczynia wlewa się trzy niemieszające się ciecze: wodę, naftę i rtęć. W jakiej kolejności są ułożone? Uzasadnij swoją odpowiedź.
- 1. Życie można znaleźć: a) w dowolnym miejscu biosfery; b) gdziekolwiek na Ziemi; c) gdziekolwiek w biosferze, z wyjątkiem Antarktydy i Arktyki.