Технический форум

Технический форум (http://www.tehnari.ru/index.php)
-   Помощь студентам (http://www.tehnari.ru/forumdisplay.php?f=41)
-   -   Задача о счастливых числах (http://www.tehnari.ru/showthread.php?t=93631)

Стася 08.01.2014 17:24
Задача о счастливых числах
 
Вложений: 1
Вот такая задачка, нужно решить в Паскале

Я начала делать через массивы, но абсолютно не представляю, как найти количество счастливых чисел, с суммой цифр 13. Помогите пожалуйста

Код:
Const n=6;
vect_min = 0;
vect_max = 9;

Var        i, s, s1, s2 : Integer;                                                       
A:Array[1..n] Of Integer;

Begin
Randomize;       
For i:=1 To n Do       
Begin
A[i]:=Random(vect_max-vect_min + 1) + vect_min;
Write(A[i]);
End;

WriteLn;

s1:=A[1]+A[2]+A[3];       
s2:=A[4]+A[5]+A[6];       

If s1=s2 then
WriteLn('билет "счастливый" :)')else
WriteLn('увы, билет не счастливый :( ');

End.

Vladimir_S 08.01.2014 17:29
Цитата:
Сообщение от Стася (Сообщение 989638)
Вот такая задачка, нужно решить в Паскале
Ладно, сейчас нарисую.

AlexZir 08.01.2014 17:38
Как один из вариантов :)
Цитата:
n:=0;
for x:=0 to 9 do
for y:=0 to 9 do
for z:=0 to 9 do
if x+y+z=13 then inc(n);
У меня получилось, что таких чисел всего может быть 75 :)

Стася 08.01.2014 17:41
Спасибо)) Сейчас попробую)

Vladimir_S 08.01.2014 17:43
Лёша, по-моему, в условии не полусумма, а вся сумма должна равняться 13. Нет?

AlexZir 08.01.2014 17:45
Не, сравнивается сумма троек цифр шестизначного числа :)
Если сумма 1,2,3 цифр равна сумме 4,5,6 цифр, то такой билет считается счастливым и незамедлительно съедается на глазах у изумленного контроллера :))
В задании нужно вычислить количество возможных комбинаций троек, в сумме равных 13.

А если общая сумма цифр числа будет равна 13, то такой билет просто не может считаться счастливым, так как не соблюдается принцип равенства суммы троек цифр. Общая сумма цифр числа счастливого билета равна удвоенной сумме одной из троек цифр.

Стася 08.01.2014 17:48
Юхуу, вроде все получилось:) еще раз спасибо

Код:
A[2]:=y;
A[1]:=x;
A[3]:=z;

c:=0;
for x:=0 to 9 do
for y:=0 to 9 do
for z:=0 to 9 do
if x+y+z=13 then inc(c);

writeln(c)
75 таких)

AlexZir 08.01.2014 17:59
Ну вы радоваться то не торопитесь, задача решена не полностью, вы еще не реализовали механизм определения счастливого числа, введенного с клавиатуры :)

Vladimir_S 08.01.2014 18:00
Цитата:
Сообщение от AlexZir (Сообщение 989646)
А если общая сумма цифр числа будет равна 13, то такой билет просто не может считаться счастливым
Ох, пардон. Заскок. Конечно, не может - по причине нечетности числа 13.

Vladimir_S 08.01.2014 18:06
Цитата:
Сообщение от Стася (Сообщение 989647)
75 таких)
А вот у меня получилось самую малость другое число: 5175. Решал "в лоб":
Код:
Var
 K,N,i:LongInt;
 Sum:Byte;
 B:boolean;

Procedure Lucky(KL:LongInt; var SL:byte; var Lu:boolean);
var
 A:Array[1..6] of byte;
 Q:LongInt;
 p,S1,S2:byte;
begin
 Q:=KL;
 for p:=6 downto 1 do
  begin
  A[p]:=Q mod 10;
  Q:=Q div 10;
  end;
 SL:=A[1]+A[2]+A[3];
 Lu:=(A[1]+A[2]+A[3])=(A[4]+A[5]+A[6]);
end;

Begin
 Repeat
  Write('Number = ');
  Readln(K);
  If (K<100000) or (K>999999) then Writeln('Number must contain 6 digits!');
 Until (K>99999) and (K<1000000);
 Lucky(K,Sum,B);
 Writeln(B);
 N:=0;
 for i:=100000 to 999999 do
  begin
  Lucky(i,Sum,B);
  if B and (Sum=13) then Inc(N);
  end;
 Writeln(N,' numbers');
 Readln
End.

AlexZir 08.01.2014 18:08
Владимир, как??? Там же всего 10*10*10=1000 комбинаций цифр.
Хотя, если вспомнить теорию вероятности...

Vladimir_S 08.01.2014 18:22
Цитата:
Сообщение от AlexZir (Сообщение 989656)
Владимир, как???
Да очень просто!
1. Ограничимся шестизначными числами, т.е. 0 в первой позиции не допускаем. Тогда мы можем найти полное число троек, дающих в сумме 13:
Код:
Var
 N,x,y,z:byte;
Begin
 N:=0;
 for x:=1 to 9 do
  for y:=0 to 9 do
  for z:=0 to 9 do
    if (x+y+z)=13 then Inc(N);
 Writeln(N);
 Readln
End.
Результат: 69.
Но!!! "Счастливым" является число, в котором СУММЫ троек цифр совпадают. Суммы, а не обязательно сами тройки! То есть "счастливой" является комбинация ЛЮБОЙ из 69 торек С ЛЮБОЙ ДРУГОЙ из них же! Вот так. И плюс к тому, в младшей тройке первый 0 допускается, т.е. там их - 75. Отсюда полное число комбинаций есть 69*75=5175. Уф, совпало!
А вообще проще не умствовать и не лезть в дебри комбинаторики, а решить простым перебором.

AlexZir 08.01.2014 18:26
А почему первая цифра не может быть равной 0? как насчет такого варианта 067139? Такие номера часто встречаются, например, в кинотеатрах, как вспомню, так и начинает голова чесаться (мы раньше перед киносеансом в щелбаны играли на цифры в номерах билетов) :)

Стася 08.01.2014 18:29
Цитата:
Сообщение от AlexZir (Сообщение 989652)
Ну вы радоваться то не торопитесь, задача решена не полностью, вы еще не реализовали механизм определения счастливого числа, введенного с клавиатуры :)
Ну это-то уже не сложно:)

Цитата:
Сообщение от Vladimir_S (Сообщение 989654)
А вот у меня получилось самую малость другое число: 5175.
А вот это уже проблема)

AlexZir 08.01.2014 18:31
Это-то как раз не проблема и вполне объяснимо :)
Если следовать логике Владимира, первая тройка без 0 в начале дает 69 вариантов, вторая тройка даст вычисленные нами 75 комбинаций, в целом по билету будет 69*75=5175 комбинаций. Полное же количество вариантов с 0 в начале первой тройки даст нам 75*75=5625 комбинаций номеров :))

Vladimir_S 08.01.2014 18:34
Цитата:
Сообщение от AlexZir (Сообщение 989661)
А почему первая цифра не может быть равной 0? как насчет такого варианта 067139?
Ну, вообще-то речь в задаче идет о ШЕСТИЗНАЧНЫХ числах, а 067139 вообще-то пятизначное. Но если допустить и такие, то ответ будет 75²=5625.

Vladimir_S 08.01.2014 18:36
Цитата:
Сообщение от AlexZir (Сообщение 989664)
даст нам 75*75=5625 комбинаций номеров
Цитата:
Сообщение от Vladimir_S (Сообщение 989665)
ответ будет 75²=5625.
Уф, ну, кажись, справились в два ума! :D

AlexZir 08.01.2014 18:38
Формально вы правы, но на деле шестизначные номера билетов могут начинаться и с первых трех нулей и против этого ничего не поделаешь :))

Все дело в некорректности формулировки задачи. Следовательно, во всем виноват преподаватель, разработавший этот билет. На том и остановимся :D

Vladimir_S 08.01.2014 18:41
Цитата:
Сообщение от AlexZir (Сообщение 989667)
Формально вы правы, но на деле шестизначные номера билетов могут начинаться и с первых трех нулей и против этого ничего не поделаешь :))
Ха! Так ведь в задаче-то речь вовсе не о билетах, никакие билеты там не фигурируют, а именно о ШЕСТИЗНАЧНЫХ ЧИСЛАХ.

AlexZir 08.01.2014 18:45
задача решается тривиально в этом случае :)
Цитата:
var a,b,c,x,y,z,n:integer;
begin
n:=0;
for a:=1 to 9 do
for b:=0 to 9 do
for c:=0 to 9 do
for x:=0 to 9 do
for y:=0 to 9 do
for z:=0 to 9 do
if ((x+y+z=13) or (a+b+c=13)) and (a+b+c=x+y+z) then inc(n);
writeln('n=',n);
readln
end.

Vladimir_S 08.01.2014 18:45
А вообще, Лёша, мне кажется, запутали мы бедную Стасю совершенно. Поди, уж сама не рада, что к нам обратилась. Надо как-нибудь ее выпутать. :D

Стася 08.01.2014 18:46
Цитата:
Сообщение от AlexZir (Сообщение 989664)
Если следовать логике Владимира, первая тройка без 0 в начале дает 69 вариантов, вторая тройка даст вычисленные нами 75 комбинаций, в целом по билету будет 69*75=5175 комбинаций. Полное же количество вариантов с 0 в начале первой тройки даст нам 75*75=5625 комбинаций номеров :))
Ну эти моменты с преподавателем выясним, если что) зато весело будет, глядишь, он про остальные вопросы и не вспомнит:))

Vladimir_S 08.01.2014 18:49
Цитата:
Сообщение от AlexZir (Сообщение 989671)
задача решается тривиально в этом случае
Ну нет, не пойдёт! Это даёт в ответе 144. Надо так:
Код:
var
 n,m,x,y,z:integer;
begin
 n:=0;
 for x:=1 to 9 do
  for y:=0 to 9 do
  for z:=0 to 9 do
    if x+y+z=13 then inc(n);
 m:=0;
 for x:=0 to 9 do
  for y:=0 to 9 do
  for z:=0 to 9 do
    if x+y+z=13 then inc(m);
 writeln('n=',n*m);
 readln
end.

AlexZir 08.01.2014 18:57
Я уже исправил, там надо дополнительное условие дописать, смотрите еще раз :))
Цитата:
var a,b,c,x,y,z,n:integer;
begin
n:=0;
for a:=1 to 9 do
for b:=0 to 9 do
for c:=0 to 9 do
for x:=0 to 9 do
for y:=0 to 9 do
for z:=0 to 9 do
if (x+y+z=13) and (a+b+c=13) then inc(n);
writeln('n=',n);
readln
end.
Как говорится, не умом, так брУтом :D

А в целом для решения задачи в целом нафиг не нужно было заводить массив, можно было обойтись дополнительной переменной :))

Полное решение у меня есть где-то в загашниках, лет семь назад с детишками разбирали эту задачу от и до на 4 языках программирования, а сегодня сам еле-еле вспомнил решение :)) А всё некорректная формулировка задачи виновата :D

Vladimir_S 08.01.2014 19:06
Цитата:
Сообщение от AlexZir (Сообщение 989678)
if ((x+y+z=13) or (a+b+c=13)) and (a+b+c=x+y+z) then inc(n);
Избыточно! Можно короче:
if (x+y+z=13) and (a+b+c=13) then inc(n);
Кроме того - нерационально: мой вариант (с n и m) предполагает 2000 прохождений цикла, а Ваш - 1000000 (грубо говоря). Тогда уж проще тупым перебором, как у меня в программе. Те же 900000.

AlexZir 08.01.2014 19:14
Можно, но не нужно.
И вообще, хоть и с избыточным кодом, но моё, не стыренное :))

Есть фирмы, где программистам платят по количеству строк кода, так там такое накручивают, что мой избыточный код - не более чем шалость :), но вы правы, исправлю сейчас.

Насчет неоптимальности алгоритма - я же предупредил, что это вариант тупого перебора 9*10*10*10*10*10=900000 значений aka брут :))


Часовой пояс GMT +4, время: 10:55.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.