Счастливый билетик

Вчера речь зашла о ‘счастливых талончиках’, если кто на общественном транспорте не ездит то это такие талончики у которых серийный номер состоит из 6 цифр и сумма первых трёх равна сумме последних трёх. Так вот стало очень интересно какая вероятность того что тебе попадется ‘счастливый талончик’, для этого я решил написать функцию на PHP, но Apache под руками не оказалось и я написал на JavaScript. Сначала я думал что оптимальный алгоритм это разделение строки на две части, сложение цифр первой и второй половины, и сравнение.


function is_lucky(num){
	num = num.toString(); // на всякий случай
	var l = num.length, part = [], sum = [0,0];
	if (l%2 || !/^[0-9]+$/.test(num))
		return false;
	part[0] = num.substring(0,l/2).split("");
	part[1] = num.substring(l/2,l).split("");
	for(var i in part)
		for(var j in part[i])
			sum[i] += parseInt(part[i][j]);
	return sum[0] == sum[1];
}

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


function is_lucky(num){
	var l = num.length, sum = 0;
	if (l%2 || !/^[0-9]+$/.test(num))
		return false;
	for(var i in num)
		sum += parseInt(num[i]) * (i<l/2?1:-1);
	return !sum;
}

Можно проверить результат самому :)

Реализация на PHP


function is_lucky($num){
	$l = strlen($num);
	$sum = 0;
	if ($l%2 || !preg_match("/^[0-9]+$/", $num))
		return false;
	for($i=0;$i<$l;$i++)
		$sum += $num[$i] * ($i<$l/2?1:-1);
	return !$sum;
}

А еще я подумал что раз уж PHP и JavaScript языки нетипизированные то стоит проверять что засунули в функцию и добавил туда регулярку /^[0-9]+$/

Реализация на Java


package ua.kiev.mabp;

/**
 * Created by IntelliJ IDEA.
 * User: CTAPbIu_MABP
 * Date: 07.03.2009
 * Time: 11:40:21
 */

public class LuckyCoupon {
    public static void main(String[] args) {
        System.out.print(isLucky(463571));
    }

    public static Boolean isLucky(Integer num) {
        char[] c = num.toString().toCharArray();
        int sum=0;
        for (int i=0,l=c.length;i<l;i++)
            sum += c[i] * (i<l/2?1:-1);
        return sum==0;
    }
}

Но вернемся к тому зачем нам это нужно было, а нужно было посчитать количество счастливых билетиков. Для этого чуть усложним наш класс добавив в метод main цикл и дополнительный метод который из числа в формате ‘123’ сделает число в формате ‘000123’ и передаст на обработку уже имеющемуся методу для проверки.


package ua.kiev.mabp;

/**
 * Created by IntelliJ IDEA.
 * User: CTAPbIu_MABP
 * Date: 07.03.2009
 * Time: 11:40:21
 */

public class LuckyCoupon {
    public static void main(String[] args) {
        int counter = 0;
        for(int i=0;i<1000000;i++)
            if (isLucky(i))
                counter++;
        System.out.print(counter);
    }

    public static Boolean isLucky(Integer num) {
        int l = 6 - num.toString().length();
        String str = "";
        for (int i=0;i<l;i++)
            str += "0";
        return isLucky(str+num);
    }

    public static Boolean isLucky(String num) {
        char[] c = num.toCharArray();
        int sum=0, i=0, l=c.length;
        while (i<l)
            sum += c[i] * (i++<l/2?1:-1);
        return sum==0;
    }
}

В результате получим число 55252, далее пользуясь только калькулятором узнаем что 55252/1000000*100 = 5,5252% . То есть вероятность получить из рук кондуктора счастливый билетик чуть более чем пять с половиной процентов, а те кто играет в линейку или вов знают что это достаточно большой шанс.

Но удивляет другое удивляет симметричность появления таких числе, я хотел нарисовать график, но подумал что график на 1000 позиций будет очень большим поэтому приведу тут только часть матрицы. Ах да матрицы… Матрица получается в том случаи если посчитать сколько ‘счастливых талончиков’ в каждой тысяче, и записывать в ряд делая обрыв строки после каждого значения. В общем не с моим талантом объяснять смотрите и запускайте код. Этим надо заменить метод main из прошлого примера.


    public static void main(String[] args) {
        int counter = 0;
        Integer[] num = new Integer[1000];
        for(int i=0;i<1000000;i++)
            if (isLucky(i)){
                counter++;
                Integer d = ((Double)Math.floor(i++/1000)).intValue();
                if (num[d] == null)
                    num[d] = 0;
                num[d]++;
            }
        for (int i=0;i<1000;i++){
            String str = num[i].toString();
            System.out.print((str.length()<2?"0"+str:str) + (i%10==9?"\n":" "));
        }
    }

Так вот вернемся к матрице, она получаеться вот такая

01 03 06 10 15 21 28 36 45 55
03 06 10 15 21 28 36 45 55 63
06 10 15 21 28 36 45 55 63 69
10 15 21 28 36 45 55 63 69 73
15 21 28 36 45 55 63 69 73 75
21 28 36 45 55 63 69 73 75 75
28 36 45 55 63 69 73 75 75 73
36 45 55 63 69 73 75 75 73 69
45 55 63 69 73 75 75 73 69 63
55 63 69 73 75 75 73 69 63 55

Cледующая часть будет начинаться с 03 (06, 10, 15 …) и заканчиваться на 63 (69, 73, 75…), тоесть самый правый столбик с каждым цыклом переходит в первый ряд и так пока 01 не окажеться в правом нижнем углу.

А в школе мне математика была не интересна…

6 Комментарии “Счастливый билетик

  1. Не могли бы Вы мне помочь, я хочу на сайте сделать что-то типа игры Счастливый IP или номер телефона, или номер кошелька. Остановился на str_replace, а дальше застрял.

  2. Хорошо, а тогда кто придумал значение числа? Например «1» -это встреча, и так далие

Комментарии закрыты