* Нови факултетни номера
Публикувано на 30 ноември 2010 в раздел Математика.
Тази година решихме да променим факултетните номера на нашите студенти. Изискванията са следните:
- Числото да е от 10 цифри;
- Да съдържа в себе си всяка една от цифрите от 0 до 9 (т.е. всички цифри в него ще са различни);
- Числото да се дели на всяко едно от числата от 1 до 9.
Намерете:
- Най-малкият факултетен номер;
- Най-големият факултетен номер;
- Общото количество възможни факултетни номера.
П.П. За да не тръгне някаква лоша мълва в „Технически Университет – София“, която да ме „прочуе“, специално отбелязвам: това е просто задача – написаното по-горе не е истина :)
А може ли да започва с нула?
Третото ти условие не е коректно: Число се дели на число, а не на цифра!!!
Щом не е написано, значи може да започва с нула… Условието ще го коригирам.
Всички трябва да се делят на 9!=362880
понеже има 2 и 5 в числата от 1 до 9 значи 0 винаги ще е накрая следователно всички числа ще са 10-цифрени
пускам цикъл от i=1000 докато i*362880<9999999999
и проверявам в кои от числата i*362880 ги има всички цифри и ги запомням в масив.
резултат:
най-малък фно:
1243589760
най-голям фно:
9875416320
общо:
73
ето всички номера:
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
Е, ако можеше да стане без програма, щеше да е по-добре :) А може! Поне за първите две задачи със сигурност…
Решението ти не е нито вярно, нито математически издържано – циклите и програмирането са хубаво нещо, но тренировката на ума е по-важна.
Правилно се досети, че числото трябва да завършва на 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…
Сега да започнем за най-голямото. Удачно е да стартираме от 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 за поправката!
Всъщност защо пък да е трудна третата задача? Дано по-долу не изръся глупост, но ми изглежда логично на третата бира:
Да вземем само номерата завършващи на *120. Преди тях има 7 цифри. Просто трябва да разгледаме техните пермутации (възможни подредби) – те са общо 7! = 5040 такива номера.
Имаме обаче 13 възможни трицифрени завършвания. Следователно имаме 5040*13 = общо 65520 възможни факултетни номера.
Да грешката ми идва че въртя цикъла по 9!, а трябва по 2520 защото то съдържа всичките множители.
А според новата версия на програмата прав ли съм за решението на задача 3? Ако искаш прати сорс кода, „за да остане за поколенията“ :)
9876531420 не се дели на 8
Програмата ми е писана на foxpro, но езика е лесно разбираем и с малко желание лесно може да се преведе на други езици.
Код:
LOCAL lncnt, i, j, lcfirst, lclast, lfoundlncnt=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
Ами да, не е… ама и аз къде съм гледал? Сега ще редактирам коментара.