DP|分治四例

发表于 更新于 Valine： 本文字数： 3.7k 估计阅读时长 ≈ 3 分钟

半数单集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
//虽然很不情愿用递归（效率低）
using namespace std;
int comp(int n) {
    int ans = 1; //初始值自身，即公式中1
    if (n > 1) for (int i = 1;i <= n / 2;i++) {//循环枚举小于n/2的值
        ans += comp(i);
    }//统计个数
    return ans;
}
int main()
{
    int  n;
    cout << "输入整数：" << endl;
    cin >> n;
    cout << "半数单集有" << comp(n) << "个元素" << endl;
    return 0;
}
//所以写了个动态规划

//#include <iostream>
//using namespace std;
//#define N 1001
//int a[N];//记录下标为i的半数集个数，避免重复调用，导致时间的浪费
//int comp(int n){
//    int ans=1;
//    if(a[n]>0) return a[n];//当a[n]的值大于零时，说明已经得出结果，无需重复计算，直接返回a[n]的值
//    for(int i=1;i<=n/2;i++){
//        ans+=comp(i);
//        a[n]=ans;}//将结果ans赋给a[n]
//        return ans;
//        }
//int main()
//{
//    int n;
//    cout << "输入整数：" << endl;
//    cin>>n;
//    cout<<"半数单集有" << comp(n) <<"个元素" << endl;
//    return 0;
//}
//

因式分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
using namespace std;
vector <int> factor;
int total = 0;
int num;
void output()
{
    vector<int>::iterator v;
    v = factor.begin();
    while (v != factor.end())
    {
        cout << *v << " ";
        v++;
    }
    cout << endl;
}
void solve(int n)
{
    if (n == 1)
    {
        total++;
        cout << num << "可分解为：";
        output();//输出向量中的元素
    }
    else
        for (int i = 2; i <= n; i++)
            if (n % i == 0)
            {
                //如果i是n的因子，则将i压入栈
                factor.push_back(i);
                solve(n / i);
                factor.pop_back();
            }
}

int main()
{
    cout<<"请输入要分解的数：" << endl;
    cin >> num;
    cout << endl;
    solve(num);
    cout << endl;
    cout << "共 " << total << " 种分解方式";
    return 0;
}

取余运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
using namespace std;
long long k;
//取余运算的性质
//同余  (a * b) % k = ( (a % k) * (b * k) ) % k;
//(a * b * c) % k =  ((a % k) * (b % k) * (c % k))
long long fun(long long b, long long p)
{
    long long t;
    if (p == 0)//递归边界
        return 1;
    t = fun(b, p / 2) % k;

    if (p % 2 == 1)
    {
        return t * t * b % k;
    }
    else {
        return t * t % k;
    }
}
int main()
{
    long long b, p;
    cout<<"请输入需要求的指数次，以及除数（例如3 2 3表示（3^2）%2）" << endl;
    cin >> b >> p >> k;
    cout << b << "^" << p << " mod " << k << "=" << (fun(b, p) % k) << endl;
    return 0;
}

中值问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//问题描述：输入任意一串数字，输出这个数字串的中位数（如果数字个数为偶数，则输出中间两个数字的均值）
#include<iostream>
using namespace std;

int Partition(int r[], int first, int end);//划分
void Quicksort(int r[], int first, int end);//快速排序
double Get_mid(int r[], int n);//得到中位数

//划分
int Partition(int r[], int first, int end)//划分
{
 int i = first, j = end;
 while (i < j)
 {
  while (i < j && r[i] <= r[j])j--;
  if (i < j)
  {
   int temp = r[i];
   r[i] = r[j];
   r[j] = temp;
   i++;
  }
  while (i < j && r[i] <= r[j])i++;
  if (i < j)
  {
   int temp = r[i];
   r[i] = r[j];
   r[j] = temp;
   j--;
  }
 } 
 return i;

}
//快速排序
void Quicksort(int r[], int first, int end)
{
 int pivot;
 if (first < end)
 {
  pivot = Partition(r, first, end);//划分，pivot是轴值在序列中的位置
  Quicksort(r, first, pivot - 1);//求解子问题：对左侧序列进行快速排序
  Quicksort(r, pivot + 1, end);//对右侧序列快速排序
 }
}
//取中值

double Get_mid(int r[], int n)
{
 //偶数个数字
 if (n % 2 == 0)
  return(r[n / 2] + r[n / 2 + 1]) / 2.0;
 //奇数
 else
  return(double)r[n / 2 + 1];
}

int main()
{
 int r[100];
 int n;
 float result;
 cout << "请输入序列元素个数" << endl;
 cin >> n;
 cout << "请输入序列：" << endl;
 for (int i = 1;i <= n;i++)
 {
  cin >> r[i];
 }
 Quicksort(r, 1, n);
 cout << "次序列的中位数为：" << endl;
 cout << Get_mid(r, n) << endl;
 return 0;
}