Минимальное количество операций

Дано натуральное число N, мы имеем право применять любые из следующих операций столько раз, сколько мы хотим, чтобы в любом порядке:Минимальное количество операций

Первая операция: Добавьте 1 Данный натуральное число N; Если N равно 7, то после этого операция N становится 8. Если N равно 999, после этой операции она становится 1000.

Вторая операция: выберите любое вхождение любой цифры и замените ее на другую цифру. (475-> 479, 101 -> 111, 299 -> 199 и т. Д.)

Третья операция: добавить любую ненулевую цифру слева от десятичного представления N: 47 -> 247, 9999 -> 49999, 2474 -> 72474 и т. Д.).

Найти минимальное количество операций, необходимых для изменения N к счастливому номеру (счастливые числа - это целые положительные числа, десятичное представление которых содержит только счастливые цифры 4 и 7. Например, цифры 47, 744, 4 удачны и 5, 17, 467 не являются)

ПРИМЕРЫ:.

N = 25, ответ = 2

N = 46, ответ = 1

N = 99, ответ = 2

Я нашел эту проблему, в то время как я пытался различные проблемы на LUCKY NUMBER .. Я застрял на эту проблему ... Пожалуйста, помогите ..

источник

2012-02-01 Anonymous

У вас есть ограничение по времени? – duedl0r

есть ли какой-нибудь пример, где решение лучше, чем просто замена цифр? –

Не совсем, Но ограничения N равны 1 <= N <= 9223372036854775809 –

«добавить 1 к числу» и «добавить любой не- нулевая ведущая цифра к числу "- это красные сельди.

Минимальное количество операций - это одна цифра в N, которая не является удачной. Вы просто меняете каждый из не 4, не 7 цифр на 4 или 7.

Добавление ведущей цифры никогда не поможет вам, потому что нет необходимости делать число дольше. Добавление 1 кажется, как это могло бы помочь, но он будет делать только две вещи: либо он не переносит (когда вы добавляете цифру меньше 9), и в этом случае прямая замена может делать то же самое или переносить (когда вы добавляете к 9), и в этом случае он просто создал один или несколько несчастливых нулей, которые вам теперь придется «исправлять» с заменой цифр.

источник

2012-02-01 13:39:09 Borealid

Извините, но не могли бы вы уточнить »: либо он не несет (когда вы добавляете цифру меньше 9), и в этом случае прямая замена может делать то же самое или переносить (когда вы добавляете к 9) в этом случае он просто создал один или несколько несчастливых нулей, которые вам теперь нужно будет «исправить» с заменой цифр. ».. Или вы можете предоставить Pseudo Code. Я новичок, нахожу это немного сложным Чтобы понять. Спасибо! –

@Jack Добавление одного в 1 совпадает с заменой его на 2. Добавление одного в 2 заменяет его на 3. Единственное число, которое вы даже * считаете * добавлением одного к девяти ... Но что «фиксирует» максимум одну цифру (например, 39 + 1 = 40), и вы можете «исправить» эту цифру, просто заменив ее. Поэтому использование этого дополнения никогда не спасет вас от операции. – Borealid

Спасибо, господин Бореалид, за то, что он уяснил мои сомнения ... Я понимаю концепцию ур хорошо сейчас. –

Вы можете попробовать жадное решение:

Проверьте все цифры числа и подсчитать, сколько не 4 или 7 Возьмите отсчет от указанного выше операций, и посмотреть, если есть небольшой подсчет при добавлении только 1 к номеру вы попадете в Lucky.

Возьмите мин от обоих - это решение

Какой смысл в добавлении первых цифр в N? Это не даст вам оптимального решения.

источник

2012-02-01 13:40:13

С учетом правил, по-видимому, ответ - это количество цифр минус число 4 или 7 вхождений. Так, например, N = 25, вы заменяете каждую цифру на 4 или 7, принимая только по одному. для 46, вы берете 6 и заменяете его на 4 или 7, таким образом, ответ 1.

Вы можете попробовать непрерывный по модулю 10 оценки, чтобы проверить, если цифры 4 или 7

$x = the number 
$y = 0; #number of non 4 or 7 
while($x>0){ 
    if($x % 10 != 4 && $x % 10 != 7){ 
     $y++; 
    } 
    if($x % 10 == 0){ 
     $y +=4; 
    } 
    $x = floor($x/10); 
}

Видимо 0 не заменяемые делать некоторые изменения

источник

2012-02-01 13:41:58

только второй случай имеет важное значение. просто возьмите строку и подсчитайте, сколько цифр не равно 4 и 7

источник

2012-02-05 17:26:29 Sumit

Просто рассмотрите вторую операцию ......... и найдите количество цифр, отличных от 4 и 7 .... и вот ответ ..... не так ли .... :)

источник

2012-02-07 06:28:39

Минимальное количество операций

ответ

Смежные вопросы