2

Здравствуйте! Подскажите, как составить алгоритм по заданию?

Задание:

В американской армии считается несчастливым число 13, а в японской — 4. Перед международными учениями штаб российской армии решил исключить номера боевой техники, содержащие числа 4 или 13 (например, 40123, 13313, 12345 или 13040), чтобы не смущать иностранных коллег. Если в распоряжении армии имеется 100 тыс. единиц боевой техники и каждая боевая машина имеет номер от 00001 до 99999, то сколько всего номеров придётся исключить?

2
  • 5
    хех, а 100-тысячную боевую машину уворовали небось? ;)
    – yozh
    27 сен 2011 в 11:06
  • Вы сформулируйте, на выходе что должно быть ? Все "хорошие","плохие",количество ...
    – avp
    27 сен 2011 в 13:47

8 ответов 8

6

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

-fogbit- В [0:20] - 2 раза (4 и 14). В [0:30] - 3 раза (0, 14, 24), [0:100] - 11 раз и т.д. (Только 0-100 не 11 а 19 раз... Человек забыл посчитать, кроме числа 44 еще и 41..42....49)

Отсюда легко вывести формулу для 10 в степени x (это наше конечное число) варианты повторений числа y (однозначного отличного от нуля))) составит

9^(х-1)*10^0 + 9^(х-2)*10^1+ 9^(х-3)*10^2... до 9^0*10^х-1

(это вам подсказка, из которой можно сделать спокойно цикл). Дальше подсказывать, как разложить так же по числу 13? И потом найти общие точки? (Это самое сложное, но и самое интересное.)

3

Если можно просто перебором, то тогда лучше проверять не просто на наличие 1,3, а на наличие "13", например, регулярным выражением.

int c = 0;
for (int i = 0; i <= 99999; i++) {
    if (("" + i).matches(".*(4|13).*")) {
        c++;
    }
}
System.out.println(c);
3
  • Кстати, на [0:100] - 19 раз встречается, так как еще десяток чисел [40:49] 27 сен 2011 в 11:30
  • 2
    На практике конечно перебор (техника сейчас быстрая), а если мозги размять, тогда комбинаторика.
    – avp
    27 сен 2011 в 12:13
  • Согласен, интересная задачка, только сейчас времени подумать нет =) 27 сен 2011 в 12:14
2

Подумайте над тем фактом, что в последовательности чисел от 0 до 10 символ "4" встречается ровно 1 раз. В [0:20] - 2 раза (4 и 14). В [0:30] - 3 раза (4, 14, 24), [0:100] - 11 раз и т.д.

1
  • 4
    Ха-ха, а с 40 до 49 ?
    – avp
    27 сен 2011 в 13:49
1

А в чем проблема-то? Запускаете цикл от 1 до 99999: на каждом шаге преобразуете число в строку и в строке проверяете наличие в ней 1,3 и 4. Если все есть, инкрементируете счетчик.

3
  • Спасибо за ответ "Artem Prigoda"
    – turtles
    27 сен 2011 в 10:43
  • Помните только, что 1 и 3 числа должны быть подряд при проверке!!! Но за такой ответ я бы убил, когда давал задачу на определение, сколько чисел содержат шестерку, если считать от 1 до 1000. В вашем случае тоже с одним числом можно решить простой формулой, но с двузначным числом такое не прокатит и надо будет еще учитывать, сколько совпадут (сколько одновременно содержат оба числа), так что пока оптимально, но тупо перебором можно получить ответ.
    – Grimon
    27 сен 2011 в 10:53
  • >но за такой ответ я бы убил когда давал задачу аналогично.
    – fogbit
    27 сен 2011 в 10:57
1

имхо простое и достаточно гибкое решение, - позволяет подсунуть любые фильтры которые только взбредут в голову. нет смысла генерировать число а потом подсчитывать значения его отдельных разрядов. конвертация в строку тоже ресурсоемкая операция. а ведь можно сразу генерировать число в том виде который нам нужен: a*1 + b*10 + c*100 + ...

рекурсивно генерируем значения для всех разрядов числа (вложеность рекурсии = количество разрядов). режим читов включен!

и сам код:

import java.util.LinkedList ;
import java.util.List ;

public class DigitFilter
{
    // создаем интерфейс для фильтрации ненужных чисел    
    interface Filter
    {
        // метод принимает переменное число аргументов типов int,
        // комилятор неявно их преобразует к int []
        public boolean suite ( long... args ) ;
    }

    public static void main ( final String[] args )
    {
        // создаем фильтры
        final List < Filter > filters = new LinkedList < Filter > () ;
        filters.add ( createJapanFilter () ) ;
        filters.add ( createUSAFilter () ) ;

        // задаем количество знаков в числе
        // это число ограничено лишь максимальной вложеностью рекусии (256)
        final long order = 2 ;

        // выполняем рекурсивный поиск
        // количество обработаных позиций не передаем, пока-что их нет
        find ( filters, order ) ;
    }

    private static Filter createJapanFilter ()
    {
        return new Filter ()
        {
            @Override
            public boolean suite ( final long... args )
            {
                // пустой массив нет смысла проверять
                if ( (null == args) || (0 == args.length) )
                {
                    return true ;
                }

                // проверяем самый младший разряд числа, все старшие уже проверены
                return (4 != args[args.length - 1]) ;
            }
        } ;
    }

    private static Filter createUSAFilter ()
    {
        return new Filter ()
        {
            @Override
            public boolean suite ( final long... args )
            {
                // пустой массив нет смысла проверять
                // если в нем только 1 разряд - тоже
                if ( (null == args) || (0 == args.length) || (1 == args.length) )
                {
                    return true ;
                }

                // проверяем на 13, - предпоследний != 1 и последний 3
                if ( (1 == args[args.length - 2]) && (3 == args[args.length - 1]) )
                {
                    return false ;
                }

                return true ;
            }
        } ;
    }

    private static void find ( final List < Filter > filters, final long order, final long... args )
    {
        // все разряды числа уже обработаны, - выводим результат
        if ( 0 == order )
        {
            for ( int i = 0 ; i < args.length ; i++ )
            {
                System.out.print ( args[i] ) ;
            }
            System.out.println () ;
            return ;
        }

        // обрабатываем текущую позицию
        for ( int i = 0 ; i < 10 ; i++ )
        {
            // создаем новый массив с числовыми значениями позиций для следующдего уровня
            // number = new int []{args, i}
            // p.s. да лучше было бы использовать System.arraycopy, но так нагляднее
            final long[] value = new long[args.length + 1] ;
            for ( int j = 0 ; j < args.length ; j++ )
            {
                value[j] = args[j] ;
            }
            value[args.length] = i ;

            // проверяем соответствует ли число всем фильтрам
            boolean suitable = true ;
            for ( final Filter filter : filters )
            {
                if ( !filter.suite ( value ) )
                {
                    suitable = false ;

                    // выходим из цикла проверки, -
                    // нет смысла проверять остальные, число уже не подходит
                    break ;
                }
            }

            // пропускаем числа которые не соответствуют
            if ( !suitable )
            {
                continue ;
            }

            // спускаемся вниз. к следующему разряду числа 
            find ( filters, order - 1, value ) ;
        }
    }
}
1

В этой задаче проще считать количество хороших чисел. Пусть g(n) - количество чисел из n цифр, которые не содержат цифру 4 и цифры 13 подряд.

Как связаны g(n) и g(n - 1)? Возьмем любое число из n - 1 цифры и припишем спереди цифру от нуля до девяти:

         сколько среди них хороших
0xx...x    g(n - 1)
1xx...x    g(n - 1) - g(n - 2)
2xx...x    g(n - 1)
3xx...x    g(n - 1)
4xx...x    0
5xx...x    g(n - 1)
6xx...x    g(n - 1)
7xx...x    g(n - 1)
8xx...x    g(n - 1)
9xx...x    g(n - 1)

Случай 1xx...x нуждается в разъяснении. Всего таких чисел g(n - 1), но не все они правильные. Числа вида 13x...x не подходят. А таких хороших чисел g(n - 2) и их надо вычесть.

Со случаем 4xx...x - всё понятно: все такие числа плохие.

Суммируем таблицу, вручную оцениваем n = 0, n = 1:

g(0) = 1
g(1) = 9
g(n) = 9 * g(n - 1) - g(n - 2), n >= 2

Зная количество хороших чисел легко вычислить количество плохих:

b(n) = 10^n - g(n)

Переборные решения работают за 10^n. Формула для b - за n. В исходной задаче 10^n = 100000 и перебор быстрый. Выигрыш по времени растёт с ростом n.

public class Without_4_13 {
    public static long pow(long b, int n) {
        long p = 1;
        for (int i = 0; i < n; ++i) {
            p *= b;
        }
        return p;
    }

    public static long g(int n) {
        long a = 1;
        long b = 9;
        for (int i = 2; i < n + 1; ++i) {
            long c = 9 * b - a;
            a = b;
            b = c;
        }
        return b;
    }
    
    public static long b(int n) {
        return pow(10, n) - g(n);
    }

    public static void main(String... args) {
        for (int n = 1; n < 19; ++n) {
            System.out.println(n + " " + b(n));
        }
    }
}
$ javac Without_4_13.java && java Without_4_13 
1 1
2 20
3 289
4 3681
5 43840
6 500879
7 5564071
8 60575760
9 649617769
10 6885984161
11 72324239680
12 754032172959
13 7813965316951
14 80571655679600
15 827330935799449
16 8465406766515441
17 86361329962839520
18 878786562899040239

И даже это ещё не самое быстрое решение. В формуле для g зависимость от предыдущих значений линейная. Можно переписать её в матричном виде и применить быстрое возведение в степень. Станет быстрее настолько, что тормозить будет возведение десятки в степень, которое тоже надо будет переписать на быстрое. Всё это имеет смысл только если long для результата заменить на BigInteger и работать с действительно большими n.

0

а можно и так!!!

int count = 0;
for (int i = 0; i < 100000; i++) {
    for (int j = i; j != 0; j = j / 10) {
        int a = j % 10;
        if (a == 4) {
            count++;
            break;
        }
        int b = (j / 10) % 10;
        int answ = (b * 10) + a;
        if (answ == 13) {
            count++;
        }
    }
}
System.out.println(count);
0
public static void main(String[] args) {
    int counter = 0;
    for (int i = 99; i >= 1; i = i - 1) {
        for (int s = i; s != 0; s = s / 10) {
            if (s == (4 | 13) || s % 10 == 4
                    || (s % 10 == 3 && Math.floor(s / 10) % 10 == 1)) {
                counter = counter + 1;
                break;
            }
            break;
        }
    }
    System.out.println(counter);
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.