{"blocks":[{"type":"paragraph","data":{"text":"По условию задачи любое число этого ряда должно представлять собой произведение 3a · 5b · 7c."}},{"type":"paragraph","data":{"text":"Давайте посмотрим на список чисел, удовлетворяющих нашим требованиям:"}},{"type":"image","data":{"file":{"id":7511,"url":"//media.tproger.ru/uploads/2015/07/table.jpg"},"alt":"","title":"","caption":"","stretched":false,"withBackground":false,"withBorder":false,"width":770,"height":270,"optimizedFile":{"original":"https://media.tproger.ru/uploads/2015/07/table.jpg","alt":"Разработайте алгоритм, позволяющий найти k-e число из упорядоченного числового ряда, в разложении элементов которого на простые множители присутствуют только 3, 5 и 7 1","dimensions":{"width":770,"height":270},"additionalSizes":{"srcSet":[{"url":"https://tproger.ru/signed_image/_bRVQSHi-eiliFrn6nI92F7kSbmf6nfaiBCGF2BlUzE/rs:fill:766:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":766},{"url":"https://tproger.ru/signed_image/bkd416hvfHn6u5C89djB4JzfeEOtZVlI66fSG2vwt2Y/rs:fill:1532:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":1532},{"url":"https://tproger.ru/signed_image/ZAJKJ3Cj4snK4Jr78KlzcPK0gzAtAv0Mj7LE_3eDhpA/rs:fill:686:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":686},{"url":"https://tproger.ru/signed_image/w-GuOOVX45Oq9f5Z7gbXuiiarWxYp5Iu3S5UEYYTRJU/rs:fill:1372:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":1372},{"url":"https://tproger.ru/signed_image/tHIsqQyH9X_lQUUWuLqk5QGnxjIOjcmxxbXbh60hAK8/rs:fill:636:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":636},{"url":"https://tproger.ru/signed_image/IedEX0clJm1x0y78u6WRdvcbD8Mp-D3EpPYHN2IgIq0/rs:fill:1272:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":1272},{"url":"https://tproger.ru/signed_image/L0cIOluanojaPnWJYDTllxsiy6gzfSM1G4r-5Ev2OzM/rs:fill:466:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":466},{"url":"https://tproger.ru/signed_image/1g52Wiw2GHF_nMHgXOzf_DiE1862BUrIr0I5UUlEaZo/rs:fill:932:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNy90YWJsZS5qcGc","dpr":1,"width":932}],"sizes":[{"media":"(min-width: 1441px)","size":"766px"},{"media":"(min-width: 1281px)","size":"686px"},{"media":"(min-width: 1281px)","size":"766px"},{"media":"(min-width: 961px)","size":"766px"},{"media":"(min-width: 671px)","size":"636px"},{"media":"(min-width: 500px)","size":"466px"}]}}}},{"type":"paragraph","data":{"text":"Поскольку 3a-1 · 5b · 7c < 3a · 5b · 7c, то число 3a-1 · 5b · 7c должно попасть в список, как и все перечисленные далее числа:"}},{"type":"list","data":{"items":["3a-1 · 5 · 7c","3a · 5b-1 · 7c","3a · 5b · 7c-1"],"style":"unordered"}},{"type":"paragraph","data":{"text":"Другой способ — представить каждое число в следующем виде:"}},{"type":"list","data":{"items":["3 · (некоторое предыдущее число из числового ряда);","5 · (некоторое предыдущее число из числового ряда);","7 · (некоторое предыдущее число из числового ряда)."],"style":"unordered"}},{"type":"paragraph","data":{"text":"Мы знаем, что Ak можно записать как (3, 5 или 7) · (некоторое значение из { A1, …, Ak-1}). Мы также знаем, что Ak является следующим числом в данном ряду. Поэтому Ak должно быть наименьшим «новым» числом, которое может быть получено умножением каждого значения в списке на 3, 5 или 7."}},{"type":"paragraph","data":{"text":"Как найти Ak? Мы можем умножить каждое число в списке на 3, 5 или 7 и найти наименьший новый результат. Но такое решение потребует O(k2) времени. Неплохо, но можно сделать и лучше."}},{"type":"paragraph","data":{"text":"Вместо умножения всех элементов списка на 3, 5 или 7 можно рассматривать каждое предыдущее значение как основу для расчета трёх последующих значений. Таким образом, каждое число Ai может использоваться для формирования следующих форм:"}},{"type":"list","data":{"items":["3 · Ai","5 · Ai","7 · Ai"],"style":"unordered"}},{"type":"paragraph","data":{"text":"Эта идея поможет нам спланировать все заранее. Каждый раз, когда мы добавляем в список число Ai, мы держим значения 3Ai, 5Ai и 7Ai в «резервном» списке. Чтобы получить Ai+1, достаточно будет найти наименьшее значение во временном списке."}},{"type":"paragraph","data":{"text":"Наш код может быть таким:"}},{"type":"code","data":{"code":"public static int removeMin(Queue q) {\r\n int min = q.peek();\r\n for(Integer v : q) {\r\n if (min >v){\r\n min=v;\r\n }\r\n }\r\n while (q.contains(min)) {\r\n q.remove(min);\r\n }\r\n return min;\r\n}\r\n \r\npublic static void addProducts(Queue q, int v) {\r\n q.add(v * 3);\r\n q.add(v * 5);\r\n q.add(v * 7);\r\n}\r\n \r\npublic static int getKthMagicNumber(int k) {\r\n if (k < 0) return 0;\r\n \r\n int val = 1;\r\n Queue q = new LinkedList();\r\n addProducts(q, 1);\r\n for(int i = 0; i < k; i++) {\r\n val = removeMin(q);\r\n addProducts(q, val);\r\n }\r\n return val;\r\n}","language":"java lazy-code"}},{"type":"paragraph","data":{"text":"Данный алгоритм гораздо лучше предыдущего, но все еще не идеален."}},{"type":"paragraph","data":{"text":"Для генерирования нового элемента Ai мы осуществляем поиск по связному списку, где каждый элемент имеет вид:"}},{"type":"list","data":{"items":["3 · предыдущий элемент;","5 · предыдущий элемент;","7 · предыдущий элемент."],"style":"unordered"}},{"type":"paragraph","data":{"text":"Давайте уберем избыточные расчеты. Допустим, что наш список имеет вид:"}},{"type":"paragraph","data":{"text":"q6 = {7A1, 5A2, 7A2, 7A3, 3A4, 5A4, 7A4, 5A5, 7A5}"}},{"type":"paragraph","data":{"text":"Когда мы ищем минимальный элемент в списке, то проверяем сначала 7A1 < min, а затем 7A5 < min. Глупо, не правда ли? Поскольку мы знаем, что A1 < A5, то достаточно выполнить проверку 7A1 < min."}},{"type":"paragraph","data":{"text":"Если бы мы разделили список по постоянным множителям, то должны были бы проверить только первое из произведений на 3, 5 и 7. Все последующие элементы будут больше."}},{"type":"paragraph","data":{"text":"Таким образом, наш список принимает вид:"}},{"type":"list","data":{"items":["Q36 = {3A4}","Q56 = {5A2, 5A4, 5A5}","Q76 = {7A1, 7A2, 7A3, 7A4, 7A5}"],"style":"unordered"}},{"type":"paragraph","data":{"text":"Чтобы найти минимум, достаточно проверить начало каждой очереди:"}},{"type":"code","data":{"code":"","language":"auto"}},{"type":"paragraph","data":{"text":"Как только мы вычислим y, нужно добавить 3y в список Q3, 5y в Q5 и 7y в Q7. Но мы хотим вставлять эти элементы, только если они отсутствуют в других списках."}},{"type":"paragraph","data":{"text":"Как, например, 3y может попасть в какой-нибудь другой список? Допустим, элемент y был получен из Q7, это значит, что y = 7x. Если 7x — наименьшее значение, значит, 3x уже было задействовано. А как мы действовали, когда увидели 3x? Правильно, мы вставили 7 · 3x в Q7. Обратите внимание, что 7 · 3x = 3 · 7x = 3y."}},{"type":"paragraph","data":{"text":"В общем виде: если мы берем элемент из Q7, он будет иметь вид 7 · suffix. Мы знаем, что 3 · suffix и 5 · suffix уже обработаны, и элемент 7 · 3 ·suffix добавлен в Q7. Единственное значение, которое мы еще не встречали — 7 · 7 · suffix, поэтому добавляем его в Q7."}},{"type":"paragraph","data":{"text":"Давайте рассмотрим пример, чтобы разобраться, как работает данный алгоритм. Инициализация:"}},{"type":"code","data":{"code":"Q3 = 3\r\nQ5 = 5\r\nQ7 = 7\r\nУдаляем min = 3, вставляем 3*3 в Q3, 5*3 в Q5, 7*3 в Q7\r\nQ3 = 3*3\r\nQ5 = 5, 5*3\r\nQ7 = 7, 7*3\r\nУдаляем min = 5. 3*5 – дубль, значит, мы уже обработали 5*3.\r\nВставляем 5*5 в Q5, 7*5 в Q7\r\nQ3 = 3*3\r\nQ5 = 5*3, 5*5\r\nQ7 = 7, 7*3, 7*5\r\nУдаляем min = 7. 3*7 и 5*7 – дубли,\r\nуже обработали 7*3 и 7*5.\r\nВставляем 7*7 в Q7\r\nQ3 = 3*3\r\nQ5 = 5*3, 5*5\r\nQ7 = 7*3, 7*5, 7*7\r\nУдаляем min = 3*3 = 9. Вставляем 3*3*3\r\nв Q3, 3*3*5 в Q5, 3*3*7 в Q7.\r\nQ3 = 3*3*3\r\nQ5 = 5*3, 5*5, 5*3*3\r\nQ7 = 7*3, 7*5, 7*7, 7*3*3\r\nУдаляем min = 5*3 =15. 3*(5*3) –\r\nдубль, так как уже обработали 5*(3*3).\r\nВставляем 5*5*3 в Q5, 7*5*3 в Q7\r\nQ3 = 3*3*3\r\nQ5 = 5*5, 5*3*3, 5*5*3\r\nQ7 = 7*3, 7*5, 7*7, 7*3*3, 7*5*3\r\nУдаляем min = 7*3 = 21. 3*(7*3) и 5*(7*3) – дубли,\r\nуже обработали 7*(3*3) и 7*(5*3). Вставляем 7*7*3 в Q7\r\nQ3 = 3*3*3\r\nQ5 = 5*5, 5*3*3, 5*5*3\r\nQ7 = 7*5, 7*7, 7*3*3, 7*5*3, 7*7*3","language":"java lazy-code"}},{"type":"paragraph","data":{"text":"Структура нашего алгоритма будет иметь вид:"}},{"type":"list","data":{"items":["Инициализируем array и очереди Q3, Q5 и Q7.","Вставляем 1 в array.","Вставляем 1·3, 1·5, 1·7 в Q3, Q5 и Q7 соответственно.","Пусть x будет минимальным элементом в Q3, Q5 и Q7.Присоединим x к magic.","Если x находится в:Q3 => присоединяем x·3, x·5 и x·7 к Q3, Q5 и Q7. Удаляем x из Q3.Q5 => присоединяем x·5 и x·7 к Q5 и Q7. Удаляем x из Q5.Q7 => присоединяем x·7 к Q7. Удаляем x из Q7.","Повторяем шаги 4-6, пока k-й элемент не будет найден."],"style":"ordered"}},{"type":"paragraph","data":{"text":"Следующий код реализует данный алгоритм:"}},{"type":"code","data":{"code":"public static int getKthMgicNumber(int k) {\r\n if (k < 0) {\r\n return 0;\r\n }\r\n int val = 0;\r\n Queue queue3 = new LinkedList();\r\n Queue queue5 = new LinkedList();\r\n Queue queue7 = new LinkedList();\r\n queue3.add(1);\r\n \r\n /* Итерация от 0 до k */\r\n for (int i = 0; i <= k; i++) {\r\n int v3 = queue3.size() > 0 ? queue3.peek() :\r\n Integer.MAX_VALUE;\r\n int v5 = queue5.size() > 0 ? queue5.peek() :\r\n Integer.MAX_VALUE;\r\n int v7 = queue7.size() > 0 ? queue7.peek() :\r\n Integer.MAX_VALUE;\r\n val = Math.min(v3,Mathmin(v5, v7));\r\n if(val == v3){ // ставим в очередь 3, 5 и 7\r\n queue3.remove();\r\n queue3.add(3 * val);\r\n queue5.add(5 * val);\r\n } else if (val == v5) {\r\n // ставим в очередь 5 и 7\r\n queue5.remove();\r\n queue5.add(5 * val);\r\n } else if (val == v7) {\r\n // ставим в очередь Q7\r\n queue7.remove();\r\n }\r\n queue7.add(7 * val);\r\n // всегда добавляем в очередь Q7\r\n }\r\n return val;\r\n}","language":"java lazy-code"}},{"type":"paragraph","data":{"text":"Если вам досталась подобная задача, приложите все усилия, чтобы ее решить, потому что это действительно трудное задание. Вы можете начать с решения «в лоб» (спорно, зато не слишком сложно), а затем попытаться оптимизировать его. Или попытайтесь найти шаблон, спрятанный в числах."}},{"type":"paragraph","data":{"text":"Интервьюер поможет, если вы будете испытывать затруднения. Не сдавайтесь! Рассуждайте вслух, задавайте вопросы и объясняйте ход ваших мыслей. Интервьюер наверняка начнет помогать вам."}},{"type":"paragraph","data":{"text":"Помните, никто не ожидает, что вы найдете идеальное решение. Ваши результаты будут сравнивать с результатами других кандидатов. Все будут находиться в одинаковых условиях."}},{"type":"paragraph","data":{"text":"Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»"}}]}

Ошибка в настройках сайта