C, PHP, VB, .NET

Дневникът на Филип Петров


* Нови факултетни номера

Публикувано на 30 ноември 2010 в раздел Математика.

Тази година решихме да променим факултетните номера на нашите студенти. Изискванията са следните:

  • Числото да е от 10 цифри;
  • Да съдържа в себе си всяка една от цифрите от 0 до 9 (т.е. всички цифри в него ще са различни);
  • Числото да се дели на всяко едно от числата от 1 до 9.

Намерете:

  1. Най-малкият факултетен номер;
  2. Най-големият факултетен номер;
  3. Общото количество възможни факултетни номера.

П.П. За да не тръгне някаква лоша мълва в "Технически Университет - София", която да ме "прочуе", специално отбелязвам: това е просто задача - написаното по-горе не е истина :)

 



12 коментара


  1. А може ли да започва с нула?
    Третото ти условие не е коректно: Число се дели на число, а не на цифра!!!

  2. Всички трябва да се делят на 9!=362880
    понеже има 2 и 5 в числата от 1 до 9 значи 0 винаги ще е накрая следователно всички числа ще са 10-цифрени
    пускам цикъл от i=1000 докато i*362880<9999999999
    и проверявам в кои от числата i*362880 ги има всички цифри и ги запомням в масив.
    резултат:
    най-малък фно:
    1243589760
    най-голям фно:
    9875416320
    общо:
    73

  3. ето всички номера:

    1243589760
    1267539840
    1389467520
    1453697280
    1463857920
    1475832960
    1639854720
    1695738240
    2148975360
    2356179840
    2397548160
    2471938560
    2537619840
    2791635840
    2847519360
    2985413760
    3124759680
    3172659840
    3178465920
    3215479680
    3458972160
    3546789120
    3572916480
    3591786240
    3691578240
    3768145920
    3917652480
    4176385920
    4712359680
    4789653120
    4921378560
    4981253760
    5179386240
    5364817920
    5369172480
    5473681920
    5841279360
    5896437120
    6179483520
    6257139840
    6329715840
    6487931520
    6785493120
    6841739520
    6894357120
    7145832960
    7236915840
    7319652480
    7459361280
    7465893120
    7519236480
    7536291840
    7538469120
    7915864320
    7964853120
    8123794560
    8143752960
    8193467520
    8347691520
    8436597120
    8472159360
    8476513920
    8593724160
    8719643520
    8947532160
    9146753280
    9257431680
    9361578240
    9641358720
    9645713280
    9715386240
    9854732160
    9875416320

  4. Решението ти не е нито вярно, нито математически издържано - циклите и програмирането са хубаво нещо, но тренировката на ума е по-важна.

    Правилно се досети, че числото трябва да завършва на 0. От тук нататък има още заключения.

    1. Всяко число се дели на 1, значи това не ни вълнува
    2. За да се дели и на 2 и на 5, то трябва да завършва на 0
    3. Всяко такова число винаги се дели на 3 и на 9 (припомнете признаците за делене на 3 и на 9) значи и това не ни вълнува
    4. Ако числото се дели на 8, то ще се дели и на 4, значи 4 не ни интересува
    5. Щом се дели на 2 и на 3, значи се дели и на 6

    => интересува ни числото да се дели на 7 и 8, както и да завършва на 0.

    Да разгледаме първо признаците за делене на 8. Разглеждаме последните три цифри:

    Ако първата цифра от тях е четна и последните две се делят на 8, то цялото число число се дели на 8. Ако първата цифра е нечетна, то извадете 4 от последните две и вижте дали полученото число се дели на 8. Ако да, то и цялото число се дели на 8. Ето възможностите:

    *120
    *160
    *240
    *320
    *360
    *520
    *560
    *640
    *720
    *760
    *840
    *920
    *960

    Забелязваме важно нещо - първите две цифри винаги се делят на 4. Ще използваме това. Дотук добре. Следва трудната част - ще решаваме задача 1. Започваме да пробваме отдалеч:

    123456***0

    Липсват цифрите 7, 8 и 9. Нито една от тях не може да направи комбинациите по-горе (от тях не може да се оформи двуцифрено число делящо се на 4). Значи не става и трябва да сменим някое. Естествено то ще е най-малкото:

    123457***0

    Липсват цифрите 6, 8 и 9. Възможно е да използваме 968 и 896 на липсващите места. Да, но не - нито 1234579680, нито 1234578960 се дели на 7. Значи продължаваме.

    Този път сменяме 7 и 5. Значи числото става 123475***0. Отново последните възможни са 968 и 896. Пробваме:
    1234759680 / 7 = 176394240 - решение
    1234758960 не се дели на 7, но това няма вече значение

    Твърдя, че най-малкото число е 1234759680

    to be continued...

  5. Сега да започнем за най-голямото. Удачно е да стартираме от 987654***0. Оставащите цифри са 3, 2 и 1. Възможните са 312 и 132. Пробваме:

    9876543120 - не
    9876541320 - не

    сменяме цифра => 987653***0 и оставащи цифри 4, 2 и 1. Възможни числа 124 и 412. Пробваме:

    9876531240 - нe
    9876534120 - не

    сменяме цифра => 987635***0 и оставащи цифри 4, 2 и 1. Отново възможни са 123 и 412:

    9876351240 - да, това е решението!
    9876354120 - не, но няма значение...

    Твърдя, че най-голямото число е 9876351240

    Остава трета задача. За съжаление съм слаб по комбинаторика и с некомпютърни средства ще се узоря много. Но не е невъзможно да се пресметне.

    П.П. Разглеждах предпоследните цифри (звездичките) по тройки за удобство - така по-бързо отпадат по няколко варианти.

    @mertol - алгоритъмът ти е грешен.

    П.С. Коментарът е редактиран на 06.12.2010 - благодаря на mertol за поправката!

  6. Всъщност защо пък да е трудна третата задача? Дано по-долу не изръся глупост, но ми изглежда логично на третата бира:

    Да вземем само номерата завършващи на *120. Преди тях има 7 цифри. Просто трябва да разгледаме техните пермутации (възможни подредби) - те са общо 7! = 5040 такива номера.

    Имаме обаче 13 възможни трицифрени завършвания. Следователно имаме 5040*13 = общо 65520 възможни факултетни номера.

  7. Да грешката ми идва че въртя цикъла по 9!, а трябва по 2520 защото то съдържа всичките множители.

  8. А според новата версия на програмата прав ли съм за решението на задача 3? Ако искаш прати сорс кода, "за да остане за поколенията" :)

  9. 9876531420 не се дели на 8

    Програмата ми е писана на foxpro, но езика е лесно разбираем и с малко желание лесно може да се преведе на други езици.
    Код:

    LOCAL lncnt, i, j, lcfirst, lclast, lfound
    lncnt=0
    i=396800
    CLEAR
    DO WHILE i*2520<9999999999
    lcx=ALLTRIM(STR(i*2520))
    IF LEN(lcx)=10 THEN
    lfound=.t.
    FOR j=0 TO 9
    IF AT(ALLTRIM(STR(j)),lcx)=0 THEN
    lfound=.f.
    EXIT
    ENDIF
    ENDFOR
    IF lfound THEN
    lncnt=lncnt+1
    IF lncnt=1 THEN
    lcfirst=lcx
    ELSE
    lclast=lcx
    ENDIF
    ENDIF
    ENDIF
    i=i+1
    ENDDO
    lcx="first="+lcfirst+CHR(13)+CHR(10)
    lcx=lcx+"last="+lclast+CHR(13)+CHR(10)
    lcx=lcx+"total="+ALLTRIM(STR(lncnt))+CHR(13)+CHR(10)
    STRTOFILE(lcx,"d:\fno.txt")

    Изход:

    first=1234759680
    last=9876351240
    total=11460

Добави коментар

Адресът на електронната поща няма да се публикува


*