ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vovanius Uryvaeff                    2:5020/175.2   02 Feb 2003  03:11:30
 To : Evgeniy Jirnov
 Subject : Шахматный номер
 -------------------------------------------------------------------------------- 
 

 Mon Jan 20 2003 21:13, Evgeniy Jirnov wrote to All:
 
  EJ> Кто знает алгоритм решения:
  EJ> Телефонный номер называется шахматным, если его цифры набираются ходом
  EJ> шахматного коня. Требуется подсчитать сколько можно набрать 6-значных
  EJ> шахматных номер начинающихся с заданной цифры. Вопрос - как? 123
  EJ> 456
  EJ> 789
  EJ>  0
 
 double hg[10][10] = {
     { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, }, /* 0 -> 4,6 */
     { 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, }, /* 1 -> 6,8 */
     { 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, }, /* 2 -> 7,9 */
     { 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, }, /* 3 -> 4,8 */
     { 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, }, /* 4 -> 0,3,9 */
     { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, /* 5 -> */
     { 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, }, /* 6 -> 0,1,7 */
     { 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, }, /* 7 -> 3,6 */
     { 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, }, /* 8 -> 1,3 */
     { 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, }, /* 9 -> 2,4 */
 } ;
 
 void mm(double s[10][10], double d[10][10]) {
     int i,j;
     for(i = 10; i--; ) for(j=10; j--; ) d[j][i] = s[j][i];
 }
 
 void mmul(double a[10][10], double b[10][10], double y[10][10]) {
     int i,j,k;
     for(i = 10; i--; ) for(j=10; j--; ) {
         y[j][i] = 0;
         for(k = 10; k--; ) y[j][i] += a[j][k]*b[k][i];
     }
 }
 
 void compmat(int q, double mr[10][10]) {
     double mq[10][10], ms[10][10];
     if(q==1) {
          mm(hg,mr);
     } else {
         compmat(q/2, mq);
         if(q&1) {
             mmul(mq,mq,ms);
             mmul(ms,hg,mr);
         } else {
             mmul(mq,mq,mr);
         }
     }
 }
 
 double numbers(int n) {
     double mr[10][10];
     double s=0;
     int i,j;
     compmat(n-1,mr);
     for(i=10; i--;) for(j=10; j--;) s+= mr[j][i];
     return s;
 }
 
 int main(int argc, char **argv)
 {
     int i;
     for(i = 2; i<513; i++) {
         printf("%d digits = %f numbers\n",i,numbers(i));
     }
     return 0;
 }
 
 во как...
 самый быстрый вроде. Считает число номеров как число путей в графе.
 
 Send Email to vovanius2000<yxo>mail. ru
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Шахматный номер   Evgeniy Jirnov   20 Jan 2003 22:13:50   Шахматный номер   Konstantin Azarov   21 Jan 2003 06:06:11   Шахматный номер   Sergey Politov   21 Jan 2003 07:42:52   Шахматный номер   Ivan Mak   21 Jan 2003 15:02:18   Re: Шахматный номер   Andrew Porohin   21 Jan 2003 21:40:10   Шахматный номер   Egor Tsygvintsev   21 Jan 2003 23:48:13   Шахматный номер   Boris Sivko   29 Jan 2003 22:07:03   Шахматный номер   Vovanius Uryvaeff   02 Feb 2003 03:11:30