Реализации алгоритмов/Подсчёт счастливых билетов: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строка 3: Строка 3:
== Python 3 ==
== Python 3 ==
<source lang="python">
<source lang="python">
def happyTickets(num):
def luckyTickets(num):
if num % 2 != 0 or num <= 0: return '# Error: invalid number'
if num % 2 != 0 or num <= 0: return '# Error: invalid number'
array = [1] * 10 + [0] * (num // 2 * 9 - 9)
array = [1] * 10 + [0] * (num // 2 * 9 - 9)
Строка 11: Строка 11:


# количество счастливых билетов среди шестизначных чисел
# количество счастливых билетов среди шестизначных чисел
print(happyTickets(6))
print(luckyTickets(6))
</source>
</source>



Версия от 14:23, 29 июля 2017

Python 3

def luckyTickets(num):
  if num % 2 != 0 or num <= 0: return '# Error: invalid number'
  array = [1] * 10 + [0] * (num // 2 * 9 - 9)
  for i in range(num // 2 - 1):
    array = [sum(array[x::-1]) if x < 10 else sum(array[x:x-10:-1]) for x in range(len(array))]
  return sum([x**2 for x in array])

# количество счастливых билетов среди шестизначных чисел
print(luckyTickets(6))

C++

#include <fstream>
int main()
{
 using namespace std;
 ofstream out("LuckyTicket.txt",ios::out);
 int i1,i2,i3,i4,i5,i6,count=0;
 for(i1=0;i1<10;i1++)
  for(i2=0;i2<10;i2++)
   for(i3=0;i3<10;i3++)
    for(i4=0;i4<10;i4++)
     for(i5=0;i5<10;i5++)
      for(i6=0;i6<10;i6++)
       if(i1+i2+i3==i4+i5+i6)
       {
        out<<i1<<i2<<i3<<" "<<i4<<i5<<i6<<"\n";
        count++;
       }
 out<<"Number of lucky tickets is "<<count<<endl;
}

C++ с длинной арифметикой

void inline count_lucky(unsigned int num_length_val)
{
  bool is_odd = (num_length_val % 2) > 0;
  unsigned int num_length = (is_odd) ? num_length_val - 1 : num_length_val;
  register unsigned int lucky=1, total=pow(10.0,(int)num_length), i;
  char *num = new char[num_length], *end=num+(num_length-1);
  register char *pos=end;
  for(i=0; i < num_length; i++)
    num[i]=0;
  while(pos>=num)
  {
     if((*pos)<9)
     {
        (*pos)++;
        if(pos==end)
        {
           if(is_lucky((unsigned char*)num, num_length))
             lucky++;
        }
        else
          pos++;
     }
     else
     {
       *pos=-1;
       pos--;
     }
  }
  printf("Lucky are %d of %d (%.3f%%)\n",(is_odd) ? lucky * 10 : lucky, (is_odd) ? total * 10 : total,((float)lucky/total*100));
  delete[] num;
}
bool inline is_lucky(unsigned char* items, unsigned int items_count)
{
  unsigned char val1=0, val2=0;
  unsigned int half = items_count >> 1;
  for(unsigned int i=0; i < half; i++)
  {
    val1 += items[i];
    val2 += items[items_count-1-i];
  }
  return (val1==val2);
}

FreeBASIC

Dim intFileNumber As Integer = FreeFile()
Open "LuckyTicket.txt" For Output Encoding "utf8" As intFileNumber
Dim As Integer i1, i2, i3, i4, i5, i6, TicketsCount
For i1 = 0 To 9
	For i2 = 0 To 9
		For i3 = 0 To 9
			For i4 = 0 To 9
				For i5 = 0 To 9
					For i6 = 0 To 9
						If i1 + i2 + i3 = i4 + i5 + i6 Then
							Print #intFileNumber, (i1 & i2 & i3) & " " & (i4 & i5 & i6)
							TicketsCount += 1
						End If
					Next i6
				Next i5
			Next i4
		Next i3
	Next i2
Next i1
Print #intFileNumber, "Количество счастливых билетов равно " & TicketsCount
Close(intFileNumber)

Ruby

n = 2 # 2n — кол-во цифр в билете
a = Array.new(n*9 + 1, 0)

('0'*n..'9'*n).each do |s|
  sum = 0
  s.each_byte {|c| sum += c - 48 }
  a[sum] += 1
end

count = a.inject {|x, sum| x + sum**2 }

puts "Number of lucky tickets: #{count}"

Pascal

Program bilet;
Var s,a,b,v,z,i:integer; {s-количество счастливых билетов, a-сумма последних трех чисел, b-сумма первых трех чисел}
Begin
s:=1; {учитываем билет с номером 000000}
for i:=1 to 999999 do {перебираем билеты от 000001 до 999999}
begin
   v:=i;
   z:=0;
   while z<3 do  begin z:=z+1; a:=v mod 10 +a; v:=v div 10 end; {считаем сумму последних трех чисел}
   while z<6 do  begin z:=z+1; b:=v mod 10 +b; v:=v div 10 end; {считаем сумму первых трех чисел}
   if a=b then s:=s+1;
   a:=0;
   b:=0;
end;
writeln(s);
end.

JavaScript

 (function(){
   var digits = {},
        i, tmp;
   for (i = 0; i <= 999; i += 1) {
        tmp = i % 10 + ((i % 100) - (i % 10)) / 10 + (i / 100) ^ 0; 
        if (digits[tmp] === undefined) {
            digits[tmp] = 1;
        } else {
            digits[tmp] += 1;
        }
   }
   tmp = 0;
   for (i in digits) {
       tmp += digits[i] * digits[i];
   }
   document.writeln( tmp );
  }());


JAVA

    public static void main(String[] args) {
        int howMuch = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(27);
        int[] arr = new int[1000];
        for(int j = 0; j < 28; j++){
            map.put(j,0);
        }
        for (int i = 0; i < 1000; i++) {
            int key = i % 10 + i / 10 % 10 + i / 100;
            map.put(key,map.get(key) + 1);
            arr[i] = key;
        }
        for (int k = 0; k < 1000; k++) {
            howMuch  = howMuch + map.get(arr[k]);
        }
        System.out.println(howMuch);
    }