实用算法实现-第 32 篇 其它

32.1 平衡三进制

PKU JudgeOnline, 1702, Eva'sBalance是一个平衡三进制问题的实例。将一个某进制数转换为平衡三进制数的方法为：先转化为用0，1，2表示的3进制，然后通过“借位”转换。也即：

若对应的系数为2，则变为-1，高一位+1。

若对应的系数为3，则变为0，高一位+1。

为0或1时不变

32.1.1实例

PKU JudgeOnline, 1702, Eva's Balance.

32.1.2问题描述

有一个天平和一套重量为3^n的砝码，每种砝码只有一个。给定一个重量，给出维持天平平衡的砝码和重物的放置方法。

32.1.3输入

3

9

5

20

32.1.4输出

empty9

1,39

1,9 3,27

32.1.5程序

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
     int cases;
     int num;
     inttri[40];
     int top;
     int i;
     int poise;
     int first;
     cin >> cases;
     for(; cases> 0; cases--){
         memset(tri, 0, sizeof(tri));
         cin >> num;
         top = 0;
         while(num!= 0){
              tri[top++] = num % 3;
              num /= 3;
         }
         for(i =0; i < top; i++){
              if(tri[i]> 1){
                   tri[i] -= 3;
                   tri[i + 1] ++;
                   if(i== top - 1)
                   {
                       top ++;
                   }
              }
         }
         poise = 1;
         first = 1;
         for(i =0; i < top; i++){
              if(tri[i]< 0){
                   if(first== 1){
                       first = 0;
                       cout << poise;
                   }else{
                       cout<< "," << poise ;
                   }
              }
              poise *= 3;
         }
         if(first== 1)
         {
              cout << "empty";
         }
         cout << "";
 
         poise = 1;
         first = 1;
         for(i =0; i < top; i++){
              if(tri[i]> 0){
                   if(first== 1){
                       first = 0;
                       cout << poise;
                   }else{
                       cout<< "," << poise ;
                   }
              }
              poise *= 3;
         }
         if(first== 1)
         {
              cout << "empty";
         }
         cout << endl;
 
     }
}

32.2 按位运算

PKU JudgeOnline, 3652, Persistent Bits.

32.3 分数的循环小数表示法

32.3.1实例

任一分数1/n (2 ≤ n ≤ 100)，均可表示为循环小数的形式。例如：

1/2= .5

1/3= .(3)

1/6= .1(6)

求1/n的循环小数表示形式中k(0 ≤ k ≤ 9)出现的次数。

32.3.2输入

35

73

70

32.3.3输出

1

1

0

32.3.4分析

由于这里的n仅是一个两位数，所以这个题目显得比较简单。

32.3.5程序

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream.h>
int a[101][10];
int b[101][100];
int main()
{
     int sum;
     int i,j;
     int divided;
     int remain;
     int n,k;
     memset(a, 0 , sizeof(a));
     memset(b, 0 , sizeof(b));
     for(i = 2;i < 10; i++)
     {
         remain = 1;
         while(remain!= 0){
              if(b[i][remain]!= 0)
              {
                   break;
              }
              b[i][remain] ++;
              remain = remain * 10;
              divided = remain/i;
              remain = remain%i;
              a[i][divided] ++;
         }
     }
     a[10][1] = 1;
     for(i = 11;i < 100; i++)
     {
         remain = 10;
         a[i][0] ++;
         b[i][1]++;
         while(remain!= 0){
/*            if(i ==12)
                   cout<<"remain"<< remain << " ";*/
              if(b[i][remain]!= 0)
              {
                   break;
              }
              /*if(i== 12)
                   cout<< "remain"  <<remain << "divided"<< divided <<endl;*/
              b[i][remain] ++;
              remain = remain * 10;
              divided = remain/i;
              remain = remain%i;
              a[i][divided] ++;
         }
     }
/*   for(i = 99; i <101; i++)
     {
         cout << i<<": ";
         for(j = 0; j< 10; j++){
              cout<< a[i][j] << " ";
         }
         cout<<endl;
     }*/
     a[100][0] = 1;
     a[100][1] = 1;
     while(cin>> n >> k){
         sum = 0;
         for(i =2; i <= n; i++){
              sum += a[i][k];
         }
         cout <<sum<<endl;
     }
     return 1;
}

32.1 参考资料

本文中没有加以注释的算法在[i]中都可以找到。本文中没有介绍的算法论述、推导也基本可以在该文中找到。

[ii]文对状态空间搜索的讨论十分细致、深入，图示也非常清晰明了，写得非常不错。

[iii]文也是介绍人工智能的非常不错的书。

[iv]文内容丰富，不过由于很多问题没有详细引入数学模型和推导证明，所以稍显复杂难懂。

[v]文中对图算法进行了综合、精细的论述，其中最惹人注目的是其中对于算法的数学模型分析，如其中的第四章。但是该文比较难懂。

[vi]文中对欧拉回路、欧拉通路、有向欧拉回路、有向欧拉通路进行了介绍。不过其中的算法描述不够精炼、清晰。

[vii]文全面介绍了最小割模型的原理和应用。

[viii]介绍了图。

本文的很多算法的实现很多都没有优化。例如Prim算法中，从集合中取出最小的一条边，并从集合中删除的实现，性能上就远不及斐波那契堆的实现。还有包含这种操作的其它算法也是如此。

本文章欢迎转载，请保留原始博客链接http://blog.csdn.net/fsdev/article

---

[i] Introduction to Algorithms, Second Edtion. Thomas H.Cormen, CharlesE.Leiserson, Ronald L.Rivest, Clifford Stein.

[ii] Artificial Intelligence, Structures and Strategies for Complex ProblemSolving. Geoge F. Luger.

[iii] Artificial Intelligence, A Modern Approach. Stuart Russell, PrterNorvig.

[iv] 算法艺术与信息学竞赛。刘汝佳，黄亮。清华大学出版社。

[v] 网络算法与复杂性分析，第二版。谢政。国防科技大学出版社。

[vi] Discrete Mathematics, Fifth Edition. John A.Dossey, Albert D.Otto,Lawrence E.Spence, Clarles Vanden Eynden.

[vii] 最小割模型在信息学竞赛中的应用。胡伯涛（Amber）。

[viii] Introduction to Gragh Theorty. Douglas B.West.