VangerAsh 14 авг 2013 в 06:54

Генерация номеров счастливых билетов

8 мин

22K

Программирование * Алгоритмы *

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

josser 14 авг 2013 в 07:24

Вот прям как нарочно, хотели написать сложнее?

$k = 0;
            for (; $k <= $iLength / 2; $k++) {

josser 14 авг 2013 в 07:26

Ааа, я понял, вы пришли в пхп из типизированого языка. Отсюда эти нелепые префиксы типов данных в переменных.

Goodkat 14 авг 2013 в 10:31

Как раз в типизированном языке префиксы типов данных не нужны, так как IDE и компиллятор подскажут вам верный тип, а в нетипизированном языке только префиксы и спасают от хаоса :)

josser 14 авг 2013 в 10:53

Я всегда думал что ету «венгерскую» нотацию пропагандировали в Microsoft во времена когда С++ еще не был популярнее С++.

Goodkat 14 авг 2013 в 11:03

С++ никогда не был популярнее С++, они всегда были примерно одинаково популярны :)

josser 14 авг 2013 в 11:04

Щи :) С# еще не был популярнее С++.

josser 14 авг 2013 в 10:56

Я программирую на пхп 9 лет. И по моему опыту я вижу что проблемы с типами данных в пхп есть только у перебежчиков с типизированых языков.
Те кто начинали с пхп не парятся и не испытывают проблем. Да и сам я ниразу не словил баг причиной которого было бы отсутствие строгой типизации.

VangerAsh 14 авг 2013 в 07:29

Если внимательнее посмотрите, там два подряд цикла с одним и тем же индексом. Поэтому и написано именно так.

jonic 14 авг 2013 в 14:50

Скажи что ты пошутил

m1el 14 авг 2013 в 07:38

Эта задача решается быстрее и понятнее в 20 строк на питоне.

# генерирует массивы из n элементов с суммой чисел s
from functools import reduce
def gen_sum(n, s, base=10):
    if s == 0:
        yield [0] * n
        return
    if n == 2:
        for i in range(max(s - base + 1, 0), min(s, base)):
            yield [i, s - i]
    else:
        for i in range(0, min(s, base)):
            for sub in gen_sum(n - 1, s - i):
                yield [i] + sub

def gen_lucky(n=3, base=10):
    for s in range(0, n * (base - 1) + 1):
        for lucky1 in gen_sum(n, s, base):
            for lucky2 in gen_sum(n, s, base):
                yield reduce(lambda a,b: a + str(b), lucky1 + lucky2, '')

for i in gen_lucky():
    print(i)

m1el 14 авг 2013 в 07:42

только в ней ошибка %)

VangerAsh 14 авг 2013 в 07:47

Питон не совсем мой язык.
Правильно ли я понял код, если в нём счастливые комбинации формируются сразу все для указанной разрядности номера и системы счисления?
Как тогда в вашем варианте реализовать последовательный постраничный вывод большого количества счастливых комбинация для, например, билетов с номерами длиной более 50 знаков?

m1el 14 авг 2013 в 08:35

Нет, номера генерируются последовательно, в памяти не хранится список номеров. Это генераторы.

tyderh 14 авг 2013 в 08:40

Нет, не все сразу

yield
ленивые вычисления

m1el 14 авг 2013 в 08:42

Если интересно — рабочая версия: gist.github.com/m1el/6229072

VangerAsh 14 авг 2013 в 09:37

Спасибо! Поизучаем немного и питон.

Mrrl 14 авг 2013 в 07:51

       static void PrintHappy(int HalfLength,int Base) {
            Happy("",0,HalfLength,Base);
        }
        static void Happy(string str,int Sum,int HalfLength,int Base) {
            int ndig=str.Length;
            if(ndig<HalfLength) {
                for(int u=0;u<Base;u++) Happy(str+u.ToString(),Sum+u,HalfLength,Base);
            } else if(ndig<2*HalfLength) {
                int maxsum=(2*HalfLength-ndig-1)*(Base-1);
                for(int u=Math.Max(0,Sum-maxsum);u<=Math.Min(Sum,Base-1);u++) {
                    Happy(str+u.ToString(),Sum-u,HalfLength,Base);
                }
            } else Console.WriteLine(str);
        }

HalfLength — половина длины билета, Base — основание системы счисления (не больше 10).

Mrrl 14 авг 2013 в 11:00

Без рекурсии получается чуть длиннее — 23 строчки на С.

#include<stdio.h>
void main(){
	int A[100],k,s,i;
	int L=3,Base=10;
	A[0]=s=k=0;
	for(;;){
		if(A[k]==Base || s<0){
			if(k==0) break;
			s+=A[k]*((k/L)*2-1);
			A[--k]++;
			s-=(k/L)*2-1;
		}else if(k==2*L-1){
			for(i=0;i<=k;i++) putchar(A[i]+'0');
			putchar('\n');
			A[k]++; s--;
		}else{
			k++;
			A[k]=s-(2*L-1-k)*(Base-1);
			if(A[k]<0) A[k]=0;
			s-=A[k]*((k/L)*2-1);
		}	  
	}
}