算法设计题目

动态规划：动态规划详解

最长公共子序列：

#include<iostream>
using namespace std;
void LCS(int i, int j, char *x, int **b) {
	if(i == 0 || j == 0) {
		return;
	}
	if(b[i][j] == 1) {
		LCS(i - 1, j - 1, x, b);
		cout << x[i];
	}else if(b[i][j] == 2) {
		LCS(i - 1, j, x, b);
	}else {
		LCS(i, j - 1, x, b);
	}
}
void LCSLength(int m, int n, char *x, char *y, int **c, int **b) {
	int i, j;
	for(i = 1; i <= m; i++) {
		c[i][0] = 0;
	}
	for(i = 1; i <= n; i++) {
		c[0][i] = 0;
	}
	for(i = 1; i <= m; i++) {
		for(j = 1; j <= n; j++) {
			if(x[i] == y[j]) {
				c[i][j] = c[i - 1][j - 1] + 1;
				b[i][j] = 1;
			}else if(c[i - 1][j] >= c[i][j - 1]) {
				c[i][j] = c[i - 1][j];
				b[i][j] = 2;
			}else {
				c[i][j] = c[i][j - 1];
				b[i][j] = 3;
			}
		}
	}
	cout << "maxlength:" << c[m][n] << endl;
	LCS(m, n, x, b);
}
int main() {
	int m,n;//连个字符串的长度 
	char *x;//第一个字符串 
	char *y;//第二个字符串 
	int **c;//存储最长公共子序列的长度。例c[i][j]为x0~xi和y0~yj的最长公共子序列的长度
	int **b;//记录每一步处理的状态，用于输出最长公共子序列 
	cin >> m >> n;
	x = new char[m + 1];
	y = new char[n + 1];
	c = new int *[m + 1];
	b = new int *[m + 1];
	for(int i = 0; i <= m; i++) {
		c[i] = new int[n + 1];
		b[i] = new int[n + 1];
	}
	for(int i = 1; i <= m; i++) {
		cin >> x[i];
	}
	for(int i = 1; i <= n; i++) {
		cin >> y[i];
	}
	LCSLength(m, n, x, y, c, b);
	for(int i = 0; i <= m; i++) {
		delete[] c[i];
		delete[] b[i];
	}
	delete[] c;
	delete[] b;
	return 0;
}

最大子矩阵和

#include<iostream>
using namespace std;
int MaxSum(int n, int *a) {
	int sum = 0, b = 0;
	for(int i = 1; i <= n; i++) {
		if(b > 0) {
			b += a[i];
		}else {
			b = a[i];
		}
		if(b > sum) {
			sum = b;
		}
	}
	return sum;
}
int MaxSum2(int m, int n, int **a) {
	int sum = 0;
	int *b = new int[n + 1];
	for(int i = 1; i <= m; i++) {
		for(int k = 1; k <= n; k++) {
			b[k] = 0;
		}
		for(int j = i; j <= m; j++) {
			for(int k = 1; k <= n; k++) {
				b[k] += a[j][k];
			}
		}
		int max = MaxSum(n, b);
		if(max > sum) {
			sum = max;
		}
	}
	delete[] b;
	return sum;
}
int main() {
	int r, c;
	int **a;
	cin >> r >> c;
	a = new int *[r + 1];
	for(int i = 1; i <= r; i++) {
		a[i] = new int[c + 1];
	}
	for(int i = 1; i <= r; i++) {
		for(int j = 1; j <= c; j++) {
			cin >> a[i][j];
		}
	}
	cout << MaxSum2(r, c, a) << endl;
	for(int i = 0; i <= r; i++) {
		delete[] a[i];
	}
	delete[] a;
	return 0;
} 

最优三角剖分

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
float w(int i, int k, int j, vector<vector<int> > v) {
	float ik,ij,kj;
	ik = sqrt(pow(v[i][0] - v[k][0], 2) + pow(v[i][1] - v[k][1], 2));
	ij = sqrt(pow(v[i][0] - v[j][0], 2) + pow(v[i][1] - v[j][1], 2));
	kj = sqrt(pow(v[k][0] - v[j][0], 2) + pow(v[k][1] - v[j][1], 2));
	return ik + ij + kj;
}
void MinWeightTriangulation(int n, float **t, int **s, vector<vector<int> > v) {
	for(int i = 1; i <= n; i++) {
		t[i][i] = 0.0;
	}
	for(int r = 2; r <= n; r++) {
		for(int i = 1; i <= n - r +1; i++) {
			int j = i + r - 1;
			t[i][j] = t[i + 1][j] + w(i - 1, i, j, v);
			s[i][j] = i;
			for(int k = i + 1; k < i + r - 1; k++) {
				int u = t[i][k] + t[k + 1][j] + w(i - 1, k, j, v);
				if(u < t[i][j]) {
					t[i][j] = u;
					s[i][j] = k;
				}
			}
		}
	}
}
int main() {
	int n;
	cin >> n;
	float **t = new float *[n];
	int **s = new int *[n];
	vector<vector<int> > v(n, vector<int>(2));
	for(int i = 0; i < n; i++) {
		cin >> v[i][0] >> v[i][1];//每个点的横纵坐标 Xi:v[i][0]  Yi:v[i][1] 
	}
	for(int i = 0; i < n; i++) {
		t[i] = new float[n];
		s[i] = new int[n];
	}
	MinWeightTriangulation(n - 1, t, s, v);
	cout << "t[1][" << n - 1 << "]=" << t[1][n - 1] << endl;
	cout << "s[1][" << n - 1 << "]=" << s[1][n - 1] << endl; 
	cout << "w(0," << s[1][n - 1] << "," << n - 1 << ")=" << w(1,s[1][n - 1], n - 1, v) << endl;
	for(int i = 0; i < n; i++) {
		delete[] t[i];
		delete[] s[i];
	}
	delete[] t;
	delete[] s;
	return 0;
}

多边形游戏（动态规划）

#include<iostream>
using namespace std;
#define NMAX 100
int N,m[NMAX + 1][NMAX + 1][2], v[NMAX + 1];
char op[NMAX + 1];
void MinMax(int n, int i, int s, int j, int &minf, int &maxf);
int PloyMax(int n, int &p);
int main() {
	int p;
	cout << "请输入多边形顶点数：";
	cin >> N;
	for(int i = 1; i <= N; i++)
	{
		cout << "请输入多边形顶点" << i << "数值:";
		cin >> v[i];
		m[i][1][0] = v[i]; 
		m[i][1][1] = v[i];
		cout << "请输入多边形边" << i << "运算符：";
		cin >> op[i];
	}
	cout << "多边形游戏首次删除第" << p <<"条边，结果为：" << PloyMax(N,p) << endl;
	return 0; 
}
void MinMax(int n, int i, int s, int j, int &minf, int &maxf) {
	int e[5];
	int a = m[i][s][0],b = m[i][s][1];
	int r = (i + s - 1) % n + 1;
	int c= m[r][j - s][0], d = m[r][j - s][1];
	if(op[r - 1] == '+')
	{
		minf = a + c;
		maxf = b + d;
	}else {
		e[1] = a * c;
		e[2] = a * d;
		e[3] = b * c;
		e[4] = d * b;
		minf = e[1];
		maxf = e[1];
		for(int r = 2; r < N; r++) {
			if(minf > e[r])
				minf = e[r];
			if(maxf < e[r])
				maxf = e[r];	
		}
	}
}
int PloyMax(int n, int &p) {
	int minf, maxf;
	for(int j = 2; j <= n; j++) {
		for(int i = 1; i <= n; i++) {
			for(int s = 1; s <= j - 1; s++) {
				MinMax(n, i, s, j, minf, maxf);
				if(m[i][j][0] > minf)
					m[i][j][0] = minf;
				if(m[i][j][1] < maxf)
					m[i][j][1] = maxf;
			}
		}
	}
	int temp = m[1][n][1];
	p = 1;
	for(int i = 2; i <= n; i++) {
		if(temp < m[i][n][1]) {
			temp = m[i][n][1];
			p = i;
		}
	}
	return temp;
}

图像压缩算法(动态规划)

#include<iostream> 
#include<cmath>  
#include<stack>
using namespace std;   
  
const int N = 7;  
  
int length(int i);  
void Compress(int n,int p[],int s[],int l[],int b[]);  
int TraceBack(int n,int l[],int b[]);  //返回有多少个段
void Out(int m,int min_len,int l[],int b[]);
  
int main()  
{  
    //int p[] = {0,10,12,15,255,1,2};//图像灰度数组 下标从1开始计数  
      int p[] = {0,255,1,5,2,1,2};
    int s[N]={0},l[N]={0},b[N]={0};  
  
    cout<<"图像的灰度序列为："<<endl;  
  
    for(int i=1;i<N;i++)  
    {  
        cout<<p[i]<<" ";  
    }  
    cout<<endl;  
  
    Compress(N-1,p,s,l,b);  
    int m=TraceBack(N-1,l,b); 
    Out(m,s[N-1],l,b);
    return 0;  
}  
  
void Compress(int n,int p[],int s[],int l[],int b[])  
{  
    int Lmax = 256,header = 11;  
    s[0] = 0;  
    for(int i=1; i<=n; i++)  
    {  
        b[i] = length(p[i]);//计算像素点p需要的存储位数  
        int bmax = b[i];  
        s[i] = s[i-1] + bmax + header;  
        l[i] = 1;  
  
        for(int j=2; j<=i && j<=Lmax;j++)  //最后一段含有一个像素，两个像素，所有像素
        {  
            //if(bmax<b[i-j+1])   //最后一个b[i-j+1]有效，是前一段当中的最大值，并不是后一段中的最大值
            if(bmax<length(p[i-j+1])) 
            {  
                bmax = length(p[i-j+1]);  
            }  
  
            if(s[i]>s[i-j]+j*bmax+header)  
            {  
                s[i] = s[i-j] + j*bmax+header;  
                l[i] = j;  
                b[i] = bmax;  //我加，跟新当前组，所需的存储位数
            }  
        }  
    }  
}  
  
int length(int i)  
{   
    int k=1;  
    i = i/2;  
    while(i>0)  
    {  
        k++;  
        i=i/2;  
    }  
    return k;
   //return ceil(log(i+1)/log(2));  
}  

int TraceBack(int n,int l[],int b[]) //从后向前检查，因而之后对应段的，最后一个存储有效
{
    stack<int>ss;
    ss.push(l[n]);
    ss.push(b[n]);
    while (n!=0)
    {
        n=n-l[n];
        ss.push(l[n]);  //l[0]=0,也被压入栈中
        ss.push(b[n]);
    }
    int i=0;
    while (!ss.empty())
    {
        b[i]=ss.top();
        ss.pop(); 
        l[i]=ss.top(); //此时　ｌ[]，用来存储，第ｉ组中，元素个数
        ss.pop();
        i++;
    }
    return i-1;
}

void Out(int m,int min_len,int l[],int b[])
{
    int i=0;
    cout<<"最小长度："<<min_len<<endl;
    cout<<"共分成："<<m<<"段"<<endl;
    for(i=i+1;i<=m;i++)
    {
        cout<<"第一个段含有"<<l[i]<<"元素.   "<<"需要存储位数"<<b[i]<<endl;
    }
}

电路布线（动态规划）

#include<iostream>
using namespace std;
void MNS(int C[], int n, int **size) {
	for(int j = 0; j < C[1]; j++)
		size[1][j] = 0;
	for(int j = C[1]; j <= n; j++) 
		size[1][j] = 1;
	for(int i = 2; i < n; i++) {
		for(int j = 0; j < C[i]; j++)
			size[i][j] = size[i - 1][j];
		for(int j = C[i]; j <= n; j++) 
			size[i][j] = max(size[i - 1][j], size[i - 1][C[i] - 1] +1);
	}
	size[n][n] = max(size[n - 1][n], size[n - 1][C[n] - 1] + 1);
}
int main() {
	int n;
	int *C = NULL;
	int **size;
	cin >> n;
	C = new int[n];
	size = new int *[n + 1];
	for(int i = 0; i <= n; i++) {
		size[i] = new int[n];
	}
	for(int i = 1; i <= n; i++) {
		cin >> C[i];
	}
	MNS(C, n, size);
	cout << "size[" << n << "]" << "[" << n << "]=" << size[n][n] << endl;
	delete[] C;
	for(int i = 0; i <= n; i++) {
		delete[] size[i];
	}
	delete[] size;
	return 0;
} 

0-1背包问题

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main() {
	int n,m;
	cin >> n >> m;
	vector<int> v(n + 1);
	vector<int> w(n + 1);
	vector<int> f(m + 1); 
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	for(int i = 1; i <= n; i++)
		cin >> w[i];
	for(int i = 1; i <= n; i++) {
		for(int j = m; j >= v[i]; j--) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << "f[" << m <<"]=" << f[m] << endl; 
	return 0;
}

p39 2-6

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<time.h>
using namespace std;
const int N = 8;
int A[N][N], B[N][N], C[N][N];
//录入矩阵元素
void input(int n, int X[][N]) {
	srand((unsigned)time(NULL));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			int x = rand() % 9 + 1;
			X[i][j] = x;
		}
	}
}
//输出矩阵
void output(int n, int X[][N]) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cout << setw(3) << setfill(' ') << X[i][j] << ' '; 
		} 
		cout << endl;
		cout << endl;
	}
}
//二阶矩阵用通用的算法来做，作为递归终止条件
void Matrix_Multiply(int A[][N], int V[][N], int C[][N]) {
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < 2; j++) {
			C[i][j] = 0;//递归前恢复原状
			for(int k = 0; k < 2; k++) {
				C[i][j] = C[i][j] + A[i][k] * B[k][j];
			} 
		}
	}
}
//矩阵相加
void Matrix_Add(int n , int A[][N], int B[][N], int C[][N]) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			C[i][j] = A[i][j] + B[i][j];
		}
	}
} 
//矩阵相减 
void Matrix_Sub(int n , int A[][N], int B[][N], int C[][N]) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			C[i][j] = A[i][j] - B[i][j];
		}
	}
} 
//strassen矩阵乘法算法
void Strassen(int n,int A[][N], int B[][N], int C[][N]) {
	int A11[N][N], A12[N][N], A21[N][N], A22[N][N]; 
	int B11[N][N], B12[N][N], B21[N][N], B22[N][N]; 
	int C11[N][N], C12[N][N], C21[N][N], C22[N][N]; 
	int M1[N][N], M2[N][N], M3[N][N], M4[N][N], M5[N][N], M6[N][N], M7[N][N];
	int AA[N][N], BB[N][N], MM1[N][N], MM2[N][N];
	if(n == 2) {
		Matrix_Multiply(A, B, C);//二阶 
	}else {
		//将矩阵拆成4快
		for(int i = 0; i < n / 2; i++) {
			for(int j = 0; j < n / 2; j++) {
				A11[i][j] = A[i][j];
				A12[i][j] = A[i][j + n / 2];
				A21[i][j] = A[i + n / 2][j];
				A22[i][j] = A[i + n / 2][j + n / 2];
				B11[i][j] = A[i][j];
				B12[i][j] = A[i][j + n / 2];
				B21[i][j] = A[i + n / 2][j];
				B22[i][j] = A[i + n / 2][j + n / 2];
			}
		}
		Matrix_Sub(n / 2, B12, B22, BB);
		//M1 = A11(B12 - B22)
		Strassen(n / 2, A11, BB, M1);
		
		Matrix_Add(n / 2, A11, A12, AA);
		//M2 = (A11 + A12)B22
		Strassen(n / 2, AA, B22, M2);
		
		Matrix_Add(n / 2, A21, A22, AA);
		//M3 = (A21 + A22)B11
		Strassen(n / 2, AA, B11, M3);
		
		Matrix_Sub(n / 2, B21, B11, BB);
		//M4 = A22(B21 - B11)
		Strassen(n / 2, A22, BB, M4);
		
		Matrix_Add(n / 2, A11, A22, AA);
		Matrix_Add(n / 2, B11, B22, BB);
		//M5 = (A11 + A22)(B11 + B22)
		Strassen(n / 2, AA, BB, M5);
		
		Matrix_Sub(n / 2, A12, A22, AA);
		Matrix_Add(n / 2, B21, B22, BB);
		//M6 = (A12 - A22)(B21 + B22)
		Strassen(n / 2, AA, BB, M6);
		
		Matrix_Sub(n / 2, A11, A21, AA);
		Matrix_Add(n / 2, B11, B12, BB);
		//M7 = (A11 - A21)(B11 + B12)
		Strassen(n / 2, AA, BB, M7);
		
		//递归结束
		Matrix_Add(N / 2, M5, M4, MM1);
		Matrix_Sub(N / 2, M2, M6, MM2);
		Matrix_Sub(N / 2, MM1, MM2, C11);
		
		Matrix_Add(N / 2, M1, M2, C12);
		
		Matrix_Add(N / 2, M3, M4, C21);
		
		Matrix_Add(N / 2, M5, M1, MM1);
		Matrix_Add(N / 2, M3, M7, MM2);
		Matrix_Sub(N / 2, MM1, MM2, C22);
		
		for(int i = 0; i < n / 2; i++) {
			for(int j = 0; j < n / 2; j++) {
				C[i][j] = C11[i][j];
				C[i][j + n / 2] = C12[i][j];
				C[i + n / 2][j] = C21[i][j];
				C[i + n / 2][j + n / 2] = C22[i][j];
			}
		}
	}  
} 
int main() {
	cout << "录入matrixA" << endl;
	input(N, A);
	cout << "录入matrixB" << endl;
	input(N, B);
	cout << "C矩阵" << endl;
	Strassen(N, A, B, C);
	output(N, C);
	cout << "A矩阵" << endl;
	output(N, A);
	cout << "B矩阵" << endl;
	output(N, B);
	return 0;
} 

p39 2-10

#include<iostream>
#include<math.h>
using namespace std;
void merge(int L[],int temp[],int left,int mid,int right) {
	int l_pos = left;
	int r_pos = mid+1;
	int pos = left;
	while(l_pos <= mid && r_pos <= right) {
		if(L[l_pos] < L[r_pos]) {
			temp[pos++] = L[l_pos++]; 
		}else {
			temp[pos++] = L[r_pos++];
		} 
	}
	while(l_pos <= mid) {
		temp[pos++] = L[l_pos++];
	}
	while(r_pos <= right) {
		temp[pos++] = L[r_pos++];
	}
	while(left <= right) {
		L[left] = temp[left];
		left++;
	}
}
void sort(int L[], int temp[], int left, int right) {
	if(left < right) {
		int j = (int)sqrt(right - left + 1);
		if(j > 1) {
			for(int i = left; i <= right; i += j) {
				sort(L, temp, i, min(i+j-1,right));
			}
		}
		for(int i = left + j - 1; i <= right; i += j) {
			merge(L, temp, left, i, min(i+j, right));
		}
	}
}
void merge_sort(int L[],int n) {
	int *temp = new int[n];
	if(!temp) {
		cout << "Failed to allocate memory!" << endl;
	}else {
		sort(L,temp,0,n-1);		
	}
}
int main() {
	int n;
	int *L = NULL;
	cin >> n;
	L = new int[n];
	for(int i = 0; i < n; i++) {
		cin >> L[i];
	}
	merge_sort(L,n);
	for(int i = 0; i < n; i++) {
		cout << L[i] << " ";
	}
    delete[] L;
	return 0;
}

p41 2-3

#include<iostream>
#include<fstream>
using namespace std;
int doset(int n) {//计算除了本身外的元素个数 
	int sum = n/2;
	if(n <= 1) {
		return 0;
	}
	for(int i = 2; i <= n/2; i++) {
		sum += doset(i); 
	}
	return sum;
}
int set(int n) {
	return doset(n) + 1;//加上本身这个一个元素。 
}
int main() {
	ifstream inf;
	ofstream ofs;
	int n;
	inf.open("input.txt");
	ofs.open("output.txt",ios::app);//以追加的形式打开output.txt文件 
	while(inf >> n) {
		ofs << set(n) << " ";//依次计算出文件中的每个元素的半数集个数并写入到output.txt文件中 
	}
	inf.close();
	ofs.close();
	return 0;
}

p42 2-6

#include<iostream>
#include<string>
#include<fstream>
using namespace std;
//求阶乘 
int f(int n) {
	if(n < 0)
	{
		return 0;
	}
	if(n == 1 || n == 0) {
		return 1;
	}
	return n * f(n - 1);
}
//将从input.txt文件中读出来的字符串存在一个数组中 
int *product_array(string str,int n) {
	int *arr = new int[n];
	for(int i = 0; i < n; i++) {
		arr[i] = str[i] - '0'; 
	}
	return arr;
}
//计算出给定字典序的字典序值 
int dict_num(int arr[],int n) {
	int result = 0;//存储最后计算出来的字典序值 
	int count = 0;//计算比本位小且在本位前数组中未出现的数字的个数 
	int k = 0;
	for(int i = 0; i < n; i++) {
		count = 0;
		for(int j = 1; j < arr[i]; j++) {
			for(k = 0; k < i; k++) {
				if(j == arr[k]) {
					break;
				}
			}
			if(k == i) {
				count ++;
			}				
		}
		result += count * f(n - 1 - i);
	}
	return result;
}
//交换两个数据在数组中的位置 
void swap(int &a,int &b) {
	int temp = a;
	a = b;
	b = temp;
}
//将数组中下标从k到m的数据进行逆序排列 
void sort(int a[],int k,int m) {
	while(k <= m) {
		swap(a[k],a[m]);
		k++;
		m--;
	}
}
//找出给定字典序的下一个字典序 
void find_next(int a[],int n) {
	for(int i = n - 1; i > 0; i--) {
		if(a[i] > a[i - 1]) {//找到出现降序的第一个元素的位置，记录下i - 1 
			for(int j = n - 1; j > 0; j--) {
				if(a[j] > a[i - 1]) {//从后往前找到第一个大于 a[i - 1]的元素 
					swap(a[j],a[i - 1]);//将这个两个元素交换位置 
					break;
				}
			}
			sort(a,i,n - 1);//将下标>=i的数组中的元素逆序排列 
			break;
		}
	}
}
int main() {
	ifstream inf;
	ofstream ofs;
	int n;
	string str;
	int *arr = NULL;
	inf.open("input.txt");
	ofs.open("output.txt",ios::app);
	if(!inf) {
		cout << "Failed to open the file!" << endl;
		return 0;
	}
	if(!ofs) {
		cout << "Failed to open the file!" << endl;
		return 0;
	}
	inf >> n;
	inf >> str;//从input.txt文件中读出相应的连个数据 
	arr = product_array(str,n);//将从input.txt文件中读出来的字符串存在一个数组arr中
	ofs << dict_num(arr,n) << '\n';//计算出给定字典序的字典序值，并将其写入到output.txt文件中 
	find_next(arr,n);//找出给定字典序的下一个字典序 
	for(int i = 0; i < n; i++) {
		ofs << arr[i];//找出给定字典序的下一个字典序,写入到文件output.txt中 
	}
	delete[] arr;//释放动态开辟的数组内存空间 
	inf.close();
	ofs.close();//关闭文件  
	return 0;
}

p43 2-7

#include<iostream>
#include<fstream>
using namespace std;
//f(4)就相当于将4这个元素插入到f(3)的各个集合中去，这样可以得出相应的递推公式 
int f(int n,int m) {//元素个数为m的集合的个数 
	if(m == 1 || n == m) {
		return 1;
	}else {
		return f(n - 1, m - 1) + m * f(n - 1, m); 
	}
}
int setNum(int n) {//将集合中元素个数分别为1-n这n中情况的总和 
	int result = 0;
	for(int i = 1; i <= n; i++) {
		result += f(n,i);
	}
	return result;
}
int main() {
	ifstream inf;
	ofstream ofs;
	int n;
	inf.open("input.txt");
	ofs.open("output.txt",ios::app);
	if(!inf) {
		cout << "Failed to open the file!" << endl;
	}
	if(!ofs) {
		cout << "Failed to open the file!" << endl;
	}
	inf >> n;
	ofs << setNum(n) << '\n';
	inf.close();
	ofs.close();
	return 0;
} 

p45 2-11

图解：

//分治法

#include<iostream>
#include<fstream>
using namespace std;
int factoring(int n) {
	int count = 0;
	if(n == 1) {
		return 1;
	}else {
		for(int i = 2; i <= n; i++) {
			if(n % i == 0) {
				count += factoring(n / i);
			}
		}
	}
	return count;
}	
int main() {
	ifstream inf;
	ofstream ofs;
	int n;
	inf.open("input.txt");
	if(!inf) {
		cout << "Failed to open the file!" << endl;
	}
	ofs.open("output.txt",ios::app);
	if(!ofs) {
		cout << "Failed to open the file!" << endl;
	}
	inf >> n;
	ofs << factoring(n) << "\n";
	return 0;
}