ITренировка — актуальные brain teaser'ы ведущих компаний

    Многие наслышаны о каверзных вопросах и задачах, которые дают на собеседованиях в Google, Microsoft, Apple, Intel, IBM, Amazon, SpaceX, Yahoo, Facebook, etc., а также российских Яндекс и Mail.ru. Они нацелены на оценку технических навыков или проверку университетских знаний, логики, мышления.

    Прежде чем подать резюме, лучше основательно подготовиться, решив хотя бы несколько таких задач. Реальные задания можно отыскать в сети. Их выкладывают как разработчики, так и сами компании.

    Этой статьей мы открываем рубрику, в которой будем публиковать несколько свежих задач или вопросов. Ответы и решения будут появляться в течение недели после публикации. Свое решение также можно предлагать в комментариях.

    На этой неделе мы публикуем 5 интересных задач, которые недавно предлагал решить разработчикам Google.

    1. Создайте случайное 4-значное четное число. Две смежные цифры должны быть разными.

    public int getNumber(){ 
    }

    2. Для введенного слова найдите следующее в лексикографическом порядке из представленных в массиве.

    Пример:

    Список слов:
    [Cat, dog, cow, donkey, zebra, monkey],
    input
    duck
    output
    monkey

    Input
    dog
    output
    donkey

    Можете ли вы использовать для решения дерево?

    public String findNextWord(List<String> words, String input){ 
    }

    3. Учитывая массив целых чисел, распечатайте все числа, удовлетворяющие следующему требованию:

    когда число больше каждого числа слева и меньше каждого числа справа.

    4. Для строковой химической формулы типа «C6H2 (NO2) 3CH3» выведите карту с ключом в качестве элемента и значением в качестве его числа. Элемент может иметь два символа, например Fe2(SO4)3

    public HashMap<Character, Integer> getCount(String chemicals){ 
    }
    

    5. В школе студент получает вознаграждение, если имеет не более 1 пропуска и 3 опозданий. Учитывая запись посещаемости студента, представленную строкой с тремя возможными символами «L» («Опоздал»), «A» (Отсутствовал), «O» («Пришел вовремя»).

    Проверьте, имеет ли студент право на вознаграждение. Пример:

    @INPUT (String) "OLLAOOOLLO"
    @RETURN (Boolean) False

    Студент не может претендовать на вознаграждение, потому что «LLA» означает, что он опоздал 3 раза подряд.

    @INPUT (String) "OLLOAOLLO"
    @RETURN (Boolean) True

    Дополнительно:

    Если известно, что длина строки посещаемости — n, сколько есть способов посещения с получением вознаграждения.

    NB

    Переводить технические тексты было непросто, даже с помощью опытных разработчиков. Судя по вашим комментариям, мы не справились, поэтому ниже приводим исходники на английском. Некоторые задачи, возможно, в оригинале тоже были приведены некорректно.

    1. Generate a random 4-digit even number: the adjacent 2 digits must be different.
    public int getNumber(){ 
    }

    2. Find the Lexicographic next word of the input word from a list of words
    Example
    Words list
    [Cat, dog, cow, donkey, zebra, monkey],
    input
    duck
    output
    monkey

    Input
    dog
    output
    donkey
    Can you use trie to solve it?

    public String findNextWord(List<String> words, String input){ 
    }

    3. Given an array of integers, print all the numbers that meet the following requirement — when the number is greater than every number on its left and smaller than every number on the right.

    4. For a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.

    element can have two chars, for example Fe2(SO4)3

    public HashMap<Character, Integer> getCount(String chemicals){ 
    } 

    5. In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
    Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
    check whether the student qualifies for the reward.

    e.g.
    @INPUT (String) "OLLAOOOLLO" 
    @RETURN (Boolean) False

    The student does not qualify for reward because «LLA» means he was late for 3 times in a row.

    @INPUT (String) "OLLOAOLLO" 
    @RETURN (Boolean) True

    Follow-up:
    If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.
    Spice IT Recruitment
    69,00
    ИТ специализированное кадровое агентство
    Поделиться публикацией

    Комментарии 45

      0
      Я не силён в химии. Что значит 3 после скобок? Должно ли это число помножатся на числа при элементах в скобках?
      И в задачи с прогулами. Из примеров следует, что опоздания играют роль только если три подряд. В условии этого не сказано.
        0
        Да, должно умножаться
        +3
        Странные задачи. Если вы ничего не перепутали, то от Гугла такого не ожидал.

        1. Некорректная постановка задачи. Тупо return 1352; формально удовлетворяет условию задачи.

        2. Примитивное решение: отсортировать массив и простейший поиск. Можно и деревом, но возни больше. Вообще оптимальный алгоритм зависит от размера массива. Для десятка элементов — любая сортировка из библиотеки и линейный поиск.

        3. Решение в один цикл и один условный оператор. Даже не интересно.

        И что значит «Учитывая массив целых чисел,»? Погрешности гуглопереводчика?

        4. Единственная задача, требующая некоторых размышлений.

        5. Банальное сканирование строки с подсчётом вхождения символов. И возврат значения логического выражения. Однако смущают примеры и комментарий.

        Из первого примера следует, что студент не получает конфетку, поскольку опоздал больше 3 раз. В комментарии же написано: «потому что «LLA» означает, что он опоздал 3 раза подряд». Отсутствие == опоздание?? И где в условии сказано, что нельзя опаздывать 3 раза подряд?

        Во втором примере тоже должно быть False, поскольку студент опаздывал более 3 раз.

        Подозреваю, что условие задачи дано (или переведено с английского?) некорректно.

        Пункт «дополнительно» n*(n-1)*(n-2)*(n-3), если следовать условию задачи из первого абзаца.
          0
          2. Отсортировать и простейший бинарный поиск. А для большого количества длинных слов оптимально использовать Trie.

          3. Неверно. Решение в два прохода и O(N) дополнительной памяти.

          4. Если честно, я не понял условие. Объясните?
          Если требуется посчитать количество атомов каждого элемента в формуле, то как, например, «Fe» влезет в ключ типа `Character`?

          5. Из контекста очевидно, что «прогул» также считается «опозданием», и что учитываются только три опоздания подряд.
          Интерес представляет дополнительная часть при таком условии. Может быть, можно придумать аналитическую формулу, но я бы решал ее динамикой.
            0
            2. До 10 элементов, скорее всего, можно не заморачиваться с бинарным поиском.

            3. Откуда два прохода и дополнительная память?

            for (size_t i = 1; i < ARR_LENGTH; ++i) {
                if (arr[i] > arr[i-1] && arr[i] < arr[i+1])
                    std::cout << arr[i] << ' ';
                }
            


            Ну ещё добавить проверку, что длина массива больше 3. И вроде как всё. Или я что-то упустил?

            5. Из контекста русского перевода как раз вообще ничего такого не следует. А вот в английском варианте, который сейчас добавили, написано: «being absent for more than once or being late for 3 times continuously». Здесь уже примеры выглядят логично: они поясняют, что подряд два опоздания и прогул тоже не допускаются. При переводе пропустили всего одно слово, и смысл задачи полностью изменился.
              0
              3. А ведь упустил. Слово «каждого». Прошу прощения.
              0
              Aivean Спасибо за исправления. При переводе допустили ошибку, заменив «trie» на «tree», что несколько меняет смысл.
              По поводу задачи 4: возможно, оригинал условия поможет вам, мы добавили его в статью.
                0
                Ниже я показал, как можно обойтись существующей памятью.

                Если очень-очень постараться, то можно и в один проход уложиться.
                Правда, потребуется второй проход уже чисто по найденной подпоследовательности, чтобы вывести её.
                Но если нам достаточно просто оставить в массиве только эту подпоследовательность, — то второй проход не потребуется.
                0
                cranium256 Спасибо за такой подробный комментарий.
                Задачи действительно от Google, их давали различным специалистам на собеседованиях, поэтому уровень сложности может отличаться.
                Возможно, наш перевод исказил суть, поэтому мы добавили оригинальный текст в теле статьи. Надеемся, что теперь задачи будут выглядеть немного интереснее, а условие станет понятнее :)!
                0
                1. Создайте случайное 4-значное четное число.
                  public int getNumber() {}

                image

                  0
                  mbait Здорово, что даже ночью у вас есть желание решать задачки :)
                  0
                  1, увы не однострочник:
                  def getNumber():
                      l = [randint(0, 4) * 2]
                      for i in 0, 0, 1:
                          d = randint(i, 8)
                          l.append(d + (l[-1] <= d))
                      return int(''.join(map(str, l[::-1])))
                  
                    0
                    longclaps чем больше вариантов решений, тем интереснее :)
                    +1

                    откуда вы это скопировали? условия половины задач некорректны / плохо переведены / непонятны, нет даже простейшей обертки кода в ```
                    и ради чего тогда вообще статья? ссылки на недельный курс "войтивайти" под ответами через неделю?

                      0
                      ngalayko Задачи скопированы с ресурса https://careercup.com/, где их постят разработчики со всего мира :)
                      Мы добавили оригиналы задач, т.к. перевод оказался частично неверным.
                      Статья чисто ознакомительного характера, чтобы все могли увидеть, что предлагают решать на собеседованиях в крупных компаниях.
                      0
                      Почему-то ни одна из приведенных задач brain teaser'ом не является. Хоть бы посмотрели сначала определение термина, чтобы не позориться.
                        0
                        alexeykuzmin0 Да, вы правы, классическим brain teaser'ом ни одна из задач не является..)
                        Заголовок рассчитан на рубрику в целом, но в этот раз это, скорее, технические задачи.
                        0
                        Задачки какие-то сомнительные.

                        1. Если нам можно препроцессинг, то проще всего создать набор всех четырёхзначных чисел, удовлетворяющих критерию (всего-то их 7290 штук, можно хоть внешним генератором нарожать сишный или шарповый файл), а затем мгновенно выбирать из массива по случайному числу в диапазоне [0..7290).
                        Если нам лень препроцессинг и плевать на равномерное распределение, то генерировать [0..10000) и брать ближайшее к случайному правильное число. Как в ЧГК ближе к концу игры.
                        Если нам и это лень и много свободного времени, то тупо долбить случайные числа, пока не налетим на правильное.
                        Если нам вообще адски не лень, то можем сочинить мега-формулу, отображающую [0..7290) на [0..10000)

                        2. Два совершенно разных случая — однократная и пакетная обработка.
                        Для однократного вызова «следующее(список, ключ)» никакие деревья нафиг не нужны. Бежим по списку и находим «минимум(фильтр(список, _ > ключ))».
                        Для пакетного вызова «следующие(список, ключи)» нужно построить дерево. Желательно — префиксное дерево. Но опять же, баланс между количеством писанины и скоростью работы. Обычный упорядоченный std::set с функцией upper_bound из плюсов — бесплатное решение, а есть ли что-то хорошее в дотнете — тут я не знаю. Возможно, что именно провал в стандартных библиотеках дотнета и заставил людей придумать такую задачу.
                        using namesace std; // чтобы не шуметь
                        vector<string> nexts(vector<string> words, vector<string> keys) {
                          set<string> sorted_words(begin(words), end(words));
                          vector<string> solutions; solutions.reserve(keys.size());
                          for (const string& key : keys) {
                            set<string>::const_iterator next = sorted_words.upper_bound(key);
                            if (next != sorted_words.end())
                              solutions.push_back(*next);
                          }
                          return solutions;
                        }
                        

                          0
                          3. Больше всех слева и меньше всех справа — это больше максимума слева и меньше минимума справа.
                          Дополнительный булев массив и ровно два забега.
                          Либо права на запись в текущий массив и константная доп.память, и опять два забега
                          int numbers[n];
                          
                          const int BAD = numbers[0]-1;  // число, заведомо не могущее быть хорошим (ибо меньше левого максимума)
                          
                          int treshold = numbers[n-1]+1;
                          for (int i=n-1; i>=0; --i) {
                            if (numbers[i] < treshold)
                              treshold = numbers[i];
                            else
                              numbers[i] = BAD;
                          }
                          treshold = numbers[0]-1;
                          for (int i=0; i<n; ++i) {
                            if (numbers[i] == BAD) continue;
                            if (numbers[i] > treshold) {
                              output(numbres[i]);
                              treshold = numbers[i];
                            }
                          }
                          
                            0
                            В четвёртой задаче надо получить брутто-формулу из структурной? Т.е. раскрыть скобки и свалить всё в кучу, да?
                            Fe2(SO4)3 = Fe2S3O6?

                            Простенький рекурсивный парсер. Много рутинной писанины.
                              0
                              nickolaym Спасибо большое за ваши ответы!
                              Мы опубликуем варианты решений немного позже. Возможно, они помогут ответить на ваши вопросы.
                              Или станут поводом для новых..))
                              0
                              5 — конечный автомат решает.
                              Состояние — это пара (количество опозданий подряд, количество пропусков всего).

                              (L,A), «O» -> (0,A) — посещение обнуляет счётчик опозданий
                              (L,A), «L» -> (L+1,A) — опоздание увеличивает счётчик
                              (L,A), «A» -> (L+1,A+1)
                              состояния остановки — (3,A) и (L,2)

                              5* — немножко марковских цепей и матричных вычислений надо.
                              Всего у нас рабочих состояний — шесть штук. (0,0), (0,1), (1,0), (1,1), (2,0), (2,1).
                              Вектор состояния S в момент t показывает, сколькими способами мы попали в то или иное состояние.
                              Для момента 0, очевидно, он равен (1,0,0,0,0,0) — мы находимся в состоянии 00.
                              Для момента t+1 вектор S' состоит из компонент:
                              S'00 = S00, — ровно один способ, не накосячить в этот раз
                              S'01 = S01 + S11 + S21 — надо придти во время, при условии, что уже однажды прогулял
                              S'10 = S00 — опоздать
                              S'11 = S01 — опоздать после старого прогула
                              S'20 = S10 — опоздать второй раз подряд
                              S'21 = S11 — опоздать второй раз подряд после старого прогула
                              Получается матрица M.
                              1 0 0 0 0 0
                              0 1 0 1 0 1
                              1 0 0 0 0 0
                              0 1 0 0 0 0
                              0 0 1 0 0 0
                              0 0 0 1 0 0
                              и вектор нового состояния — это умножение матрицы на вектор старого состояния S(t+1) = M*S(t)
                              А финальный вектор — это, соответственно, S(n) = M^(n-1) * S(t)

                              Ну и итоговый ответ — это надо просуммировать все компоненты S(n), т.е. умножить на вектор со всеми единицами E.
                              total = E * M^(n-1) * S(0).

                              Возведение матрицы в степень делается за логарифмическое время. Ну или, если это влом реализовывать, то за линейное безо всяких матриц.
                                0
                                Всем привет!
                                Как и обещали, публикуем по одному варианту решения каждой задачи. Код взят с тех же ресурсов, что и задачи. Синтаксис сохранен, комментарии к решениям также оригинальные.

                                Atention! Spoiler!

                                1. Generate a random 4-digit even number: the adjacent 2 digits must be different.
                                public int getNumber(){
                                }

                                Solution:
                                It can boil down to getting the list of integers between 1000 and 9999 (including) that have adjacent digits as different.
                                To do that we can apply memoization on the following function

                                List(d, s)
                                Lists = []

                                if d = 1
                                for i = 0 to 9 and i != s
                                Lists.add(i)
                                return Lists
                                for i in 0 to 9 and i != s
                                Lists.addAll(List(d-1, i))
                                for i in 0 to Lists.length
                                Lists[i] = (10 ^ d * s) + Lists[i]
                                return Lists

                                Call Lists(4, 1..9)
                                Then its about figure out
                                Lists[random() * (Lists.length — 1)]

                                  0
                                  2. Atention! Spoiler!

                                  Find the Lexicographic next word of the input word from a list of words
                                  Example
                                  Words list
                                  [Cat, dog, cow, donkey, zebra, monkey],
                                  input
                                  duck
                                  output
                                  monkey

                                  Input
                                  dog
                                  output
                                  donkey
                                  Can you use trie to solve it?

                                  public String findNextWord(List words, String input){
                                  }>

                                  Solution:

                                  public class FindNextLexogWord {
                                  
                                  
                                  	public static void main(String[] args) {
                                  
                                  		String[] wordList = {"Cat", "dog", "cow", "donkey", "zebra", "monkey"};
                                  		String input = "duck";
                                  		int nextLex = Integer.MIN_VALUE;
                                  		int value = 0;
                                  		String word = null;
                                  		for( int i = 0 ; i < wordList.length ; i ++ ) {
                                  			if(( value =  input.compareTo(wordList[i]))  <  0 ) {
                                  				System.out.println(value);
                                  				if( nextLex < value){ 
                                  				nextLex = value;
                                  				word = wordList[i];
                                  				}
                                  			}
                                  		}
                                  
                                  
                                  	}
                                  
                                  
                                  
                                  
                                    0
                                    А под нормальный спойлер убрать не судьба? И разметке вас никто не учил?
                                    Да и куда важнее не код решения, а рассуждения при этом. Сам код практически бесполезен.
                                    0
                                    Я вообще не программист и, возможно, вопрос глупый:
                                    2. Зачем вообще что-то сортировать, когда можно идти по списку и считать лексикографическое «расстояние» от введенного слова до текущего в просматриваемом массиве, сохраняя где-то текущий неотрицательный минимум? Функция расстояния, например, СУММА(Аi — Bi)*k^i, где i — позиция буквы в слове, Вi и Аi — буквы в введенном слове и текущем слове массива соответственно. k — константа, большая или равная длине алфавита.
                                      0
                                      3. Atention! Spoiler!
                                      Given an array of integers, print all the numbers that meet the following requirement — when the number is greater than every number on its left and smaller than every number on the right.

                                      Solution:

                                      void order(int * num, int size){
                                        int max = 0;
                                      
                                        stack<int> s;
                                        for(unsigned int i = 0; i < size; i++){
                                          if(num[i] > max){
                                            max = num[i];
                                            s.push(max);
                                          }
                                          while(!s.empty() && num[i] < s.top()){
                                            s.pop();
                                          }
                                        }
                                      
                                        while(!s.empty()){
                                          printf("%d ", s.top()) ;
                                          s.pop();
                                        }
                                        printf("\n");
                                      
                                      }
                                      
                                      
                                      int main(){
                                        int  a[] = {6, 5, 4, 3, 9, 100, 87, 64, 34, 101};
                                        int  b[] = {3, 4, 7, 1, 8, 12};
                                        order(a, 10) ;
                                        order(b, 6) ;
                                      
                                        return 0;
                                      }
                                      
                                      
                                        0
                                        4. Atention! Spoiler!
                                        For a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.
                                        element can have two chars, for example Fe2(SO4)3

                                        public HashMap<Character, Integer> getCount(String chemicals){ 
                                        }
                                        


                                        Solution:

                                         class Data{
                                        	Map<Character,Integer> elems;
                                        	int idx;
                                        	int mult;
                                        	
                                        	Data(Map<Character,Integer> mp, int i, int m){
                                        		elems = mp;
                                        		idx = i;
                                        		mult = m;
                                        	}
                                        }
                                        
                                        public Map<Character,Integer> elemCounts(String str){
                                        
                                        	Data d = elemHelp(str, 0);
                                        	if(d.mult != 1){
                                        		for(Map.Entry<Character,Integer> e: d.elems.entrySet()){
                                        			e.getValue() *= d.mult;
                                        		}
                                        	
                                        	}
                                        	return d.elems;
                                        }
                                        
                                        private Data elemHelp(String str, int i){
                                        	Map<Character,Integer> mp = new HashMap<Character,Integer>();
                                        	int mult = 1;
                                        	while(i< str.length()){
                                        		if(str.charAt(i) >= 'A' && str.charAt(i) <= 'Z'){
                                        			char elem = str.charAt(i);
                                        			int ct = 1;
                                        			if(i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
                                        				int j = i + 1;
                                        				while(j < str.length() && str.charAt(j) >= '0' && str.charAt(j) <= '9'){
                                        					j++;
                                        				}
                                        				ct = Integer.parseInt(str.substring(i + 1, j));
                                        				i = j;
                                        			}else{
                                        				i++;
                                        			}
                                        			if(mp.containsKey(elem)){
                                        				ct += mp.get(elem);
                                        			}
                                        			mp.put(elem,ct);
                                        		}else if(str.charAt(i) == '('){
                                        			Data d = elemHelp(str, i + 1);
                                        			for(Map.Entry<Character,Integer> e : d.elems.entrySet()){
                                        				e.getValue() *= d.mult;
                                        				if(mp.containsKey(e.getKey())){
                                        					e.getValue() += mp.get(e.getKey());
                                        				}
                                        				mp.put(e.getKey(),e.getValue());
                                        			}
                                        			i = d.idx;
                                        		}else{
                                        			if(i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
                                        				int j = i + 1;
                                        				while(j < str.length() && str.charAt(j) >= '0' && str.charAt(j) <= '9'){
                                        					j++;
                                        				}
                                        				mult = Integer.parseInt(str.substring(i + 1, j));
                                        				i = j;
                                        			}else{
                                        				i++;
                                        			}
                                        			break;
                                        		}
                                        		
                                        	}
                                        	return new Data(mp,mult,i);
                                        }
                                        


                                          0
                                          5. Atention! Spoiler!
                                          In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
                                          Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
                                          check whether the student qualifies for the reward.

                                          e.g. 
                                          @INPUT (String) "OLLAOOOLLO" 
                                          @RETURN (Boolean) False 
                                          


                                          The student does not qualify for reward because «LLA» means he was late for 3 times in a row.

                                          @INPUT (String) "OLLOAOLLO" 
                                          @RETURN (Boolean) True 
                                          


                                          Follow-up:
                                          If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.


                                          Solution:
                                          We can figure out this by keeping two variable one is WasAbsent and ContinousLateCount, and if WasAbsent is true when we found a new Absent, return false, or if ContinousLateCount is 2 when he/she is Late, return false.
                                          Here is how we will write the code

                                          
                                          public static boolean ShouldbeRewarded(string attendance)
                                          {
                                          	if(String.IsNullOrWhiteSpace(attendance))
                                          	{
                                          		return true;
                                          	}
                                          	boolean wasAbsent = false;
                                          	int continousLateCount = 0;
                                          	boolean WasLateLastDate = false;
                                          	for(int i = 0 ; i < attendance.Length;i++)
                                          	{
                                          		if(attendance[i] == 'A')
                                          		{
                                          			if(wasAbsent || continousLateCount >= 2)
                                          			{
                                          				return false;
                                          			}
                                          			wasAbsent = true;
                                          			continousLateCount++;
                                          		}
                                          		else if(attendance[i] == 'L')
                                          		{
                                          			if(continousLateCount >= 2)
                                          			{
                                          				return false;
                                          			}
                                          			continousLateCount++;
                                          		}
                                          		else
                                          		{
                                          			continousLateCount = 0;
                                          		}
                                          	}
                                          	return true;
                                          }
                                          	}
                                          
                                          
                                          
                                          
                                            0
                                            Задача 1. Создайте случайное 4-значное четное число. Две смежные цифры должны быть разными.

                                            Не знаю в каком контексте эта функция будет использоваться поэтому такое решение:

                                            Код на C++
                                            int getNumber() {
                                            	srand(time(0));
                                            
                                            	int result = 0;
                                            	int last = 0;
                                            
                                            	for(int i=0; i<4; i++) {
                                            		int digit;
                                            
                                            		// generate next digit 
                                            		do {
                                            			digit = rand()%10;
                                            			if (i==3) {
                                            				digit -= digit % 2;
                                            			}
                                            		} while (digit == last);
                                            
                                            		last = digit;
                                            		digit *= pow(10, 3-i);
                                            		result += digit;
                                            	}
                                            
                                            	return result;
                                            }



                                            github.com/tigertv/algorithms/tree/master/habr/328454/even4num
                                              0
                                              Насколько я понимаю, там имелось в виду, что все получающиеся числа должны быть равновероятными. У вас же вероятность получить 1234 не такая же, как вероятность получить 1246.
                                                0
                                                Хмм… А почему не такая же? Где ошибка?
                                                  0
                                                  Ошибку проще понять, если уменьшить длину чисел. Пусть они будут двузначные, вместо четырехзначных. Тогда первая цифра у нас — от 1 до 9 включительно, каждая с вероятностью 1/9. Если первая цифра 1, то вторая может быть 0, 2, 4, 6 или 8, равновероятно, то есть вероятность получить числа 10, 12, 14, 16, 18 равна 1/45. Если первая цифра 2, то вторая может быть 0, 4, 6 или 8, равновероятно, то есть, вероятность получить числа 20, 24, 26, 28 равна 1/36.
                                                  Эксперимент подтверждает, что частоты получения этих чисел как раз такие, с точностью как минимум до четырех значащих цифр.
                                                    0
                                                    Да, действительно, предыдущее событие влияет на следующее событие, и поэтому вероятность меняется. Только это не указано в условии задачи явно(к сожалению или к счастью).
                                                      0
                                                      Если делать равновероятно, то можно сгенерировать все 4 значные числа удовлетворящие критерию и сохранить в массив, а затем выбирать индекс массива случайно( передавать генератору случ. чисел размер массива минус 1 ).
                                                        0
                                                        Да, это один подход. Автор статьи так и сделал, судя по комментариям выше. Другой вариант — для каждой последней цифры подсчитать по формуле, сколько есть чисел, удовлетворяющих критерию, на нее заканчивающихся, и выбрать в соответствии с этим распределением. Потом так же выбрать вторую с конца цифру и тд.
                                                          0
                                                          Хороший способ. А если бы в задаче требовалось четную цифру в середине числа?
                                                            0
                                                            Можно с середины начинать генерить. Просто интуиция говорит мне, что формула будет проще, если сначала разобраться с четной цифрой, а потом с остальными.
                                                              0
                                                              Да, логично.) Ну, а если еще усложнить задачу. Что если последняя цифра четная, а предпоследняя может принимать 3 значения, к примеру:1,3,5?
                                                                0
                                                                Тогда формула вычисления количества будет сложнее.
                                                                  0
                                                                  ))) Что тоже логично.)
                                                                    0
                                                                    А мне интуиция говорит, что нужно генерить сначала предпоследнюю цифру(наименьший набор), затем последнюю(в порядке увеличения набора), и наконец все остальные.
                                                                      0
                                                                      А, да, первая цифра в числе выбирается после последней.(не может принимать 0)
                                                              0
                                                              если справа налево генерить, то подобная проблема возникает при 0, например x021.
                                                                0
                                                                В итоге я пришел к выводу, что нельзя сгенерировать 4-значное числа равновероятно, если использовать генерацию по одной цифре по критериям этой задачи. Чтобы генерировать равновероятно(по одной цифре) требуется знать конкретно какое количество цифр будет участвовать в выборке, а тут возникают ситуации когда в выборке следующего числа может быть различное количество(плавающее).

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое