蓝桥杯算法特训第六课【分治】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第六课【分治】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 二分查找

已知有序的序列,比如:2,3,3,5,9,9,9,12,12,13,15,22,22,22,22,25,25,23,91,95
有整数x,比如: x=23
要求找到一个刚好比x稍微大一点的元素位置

当数组较大的时候,需要二分查找加快速度。

【源代码】
【JAVA:于航】


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
public class A
{
  // 含有begin, 不含end
  static int f(int[] a, int begin, int end, int x){
    if(end-begin==1){
      if(a[begin] > x) return begin;
      return end;
    }
   
    int k = (begin+end)/2;
    if(x>=a[k]) return f(a,k,end,x);
    return f(a,begin,k,x);
  }
 
  // 求x应该插入的位置
  // return 刚好比x稍微大点的那个数的位置
  static int f(int[] a, int x){
    if(x>=a[a.length-1]) return -1;
    return f(a,0,a.length,x);
  }
 
  public static void main(String[] args){
    int[] a = {1,5,11,24,25,32,32,33,49,66,68,69,70
      ,75,88,102,114,119,120,135,146,221,294,300,302,305,333};
    System.out.println(f(a,32));
  }
}

【C:志愿者】


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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 含有begin, 不含end
int f(int* a, int begin, int end, int x)
{
  if (end - begin == 1)
  {
    if (a[begin] > x)
      return begin;
    return end;
  }

  int k = (begin + end) / 2;
  if (x >= a[k])
    return f(a, k, end, x);
  return f(a, begin, k, x);
}

// 求x应该插入的位置
// return 刚好比x稍微大点的那个数的位置
int f1(int* a,int len, int x)
{
  if (x >= a[len - 1])
    return -1;
  return f(a, 0, len, x);
}

 void main()
 {
  int a[]  = { 1, 5, 11, 24, 25, 32, 32, 33, 49, 66, 68, 69, 70, 75, 88, 102, 114, 119, 120, 135, 146, 221, 294, 300, 302, 305, 333 };
  printf("%d ",f1(a, 27, 32));

}


2. 最大序列和

数组中整数有正有负
求一连续子段,使得和最大化
例如:
2,4,-7,5,2,-1,2,-4,3
最大连续段:
5,2,-1,2

其最大和为8

【源代码】
【JAVA:于航】


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
public class A
{
  static int f(int[] a, int begin, int end){
    if(end-begin==1){
      if(a[begin] > 0) return a[begin];
      return 0;
    }
   
    int k = (begin+end)/2;
    int t1 = f(a,begin,k);
    int t2 = f(a,k,end);
   
    int t3a = 0;
    int sum = 0;
    for(int i=k-1; i>=begin; i--){
      sum += a[i];
      if(sum > t3a) t3a = sum;
    }
   
    int t3b=0;
    sum = 0;
    for(int i=k; i<end; i++){ sum += a[i]; if(sum > t3b) t3b = sum;
    }
   
    int t3 = t3a + t3b;
   
    int max = 0;
    if(t1 > max) max = t1;
    if(t2 > max) max = t2;
    if(t3 > max) max = t3;
   
    return max;
  }
 
  static int work(int[] a){
    return f(a,0,a.length);
  }
 
  public static void main(String[] args){
    System.out.println(work(new int[]{2,4,-7,5,2,-1,2,-4,3}));
  }
}

【C:志愿者】


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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int ff(int* a, int begin, int end)
{
  if (end - begin == 1)
  {
    if (a[begin] > 0)
      return a[begin];
    return 0;
  }

  int k = (begin + end) / 2;
  int t1 = ff(a, begin, k);
  int t2 = ff(a, k, end);

  int t3a = 0;
  int sum = 0;
  for (int i = k - 1; i >= begin; i--)
  {
    sum += a[i];
    if (sum > t3a)
      t3a = sum;
  }

  int t3b = 0;
  sum = 0;
  for (int i = k; i<end; i++) { sum += a[i]; if (sum > t3b)
      t3b = sum;
  }

  int t3 = t3a + t3b;

  int max = 0;
  if (t1 > max)
    max = t1;
  if (t2 > max)
    max = t2;
  if (t3 > max)
    max = t3;

  return max;
}

int work(int * a,int len)
{
  return ff(a, 0, len);
}

 void main()
 {
   int arr[] = { 2, 4, -7, 5, 2, -1, 2, -4, 3 };
   int x=work(arr, 9);
   printf("%d ", x);
}


3. 大数乘法问题

用串的形式表示大数的乘法。

即求类似: “23234845847839461464158174814792” * “6457847285617487843234535”
要求结果返回一个串。

【源代码】
【JAVA:于航】


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
import java.math.BigInteger;
public class A
{
  static String zero(int n){
    if(n==0) return "";
    if(n==1) return "0";
    return zero(n/2) + zero(n/2) + zero(n%2);
  }
 
  static String add(String a, String b){
    if(a.length()<=8 && b.length()<=8) return Integer.parseInt(a) + Integer.parseInt(b) + ""; String a1 = "0"; String a2 = a; if(a.length()>8){
      a1 = a.substring(0,a.length()-8);
      a2 = a.substring(a.length()-8);
    }
   
    String b1 = "0";
    String b2 = b;
    if(b.length()>8){
      b1 = b.substring(0,b.length()-8);
      b2 = b.substring(b.length()-8);
    }
   
    String t = add(a2,b2);
    while(t.length()<8) t = "0" + t; if(t.length()>8) return add(add(a1,b1),"1") + t.substring(1);
    return add(a1,b1) + t;    
  }
 
  static String multi(String a, String b){
    if(a.length()<=4 && b.length()<=4) return Integer.parseInt(a) * Integer.parseInt(b) + ""; if(a.length()>4){
      int k = a.length()/2;
      String a1 = a.substring(0,k);
      String a2 = a.substring(k);
     
      return add(multi(a1,b)+zero(a2.length()),multi(a2,b));
    }
   
    return multi(b,a);
  }
 
  public static void main(String[] args){
    System.out.println(multi("1234567890987654321666",
      "1234567890123456789555"));
     
    System.out.println(new BigInteger("1234567890987654321666")
      .multiply(new BigInteger("1234567890123456789555")));
  }
}

【C:志愿者】


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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
由于C原因进行字符串拼接比较繁琐,需要开辟对应长度的内存空间,全部都是用的malloc()在堆上开辟,时间紧张没有及时释放,深度递归时大量消耗内存,所以运行特别特别大的数据时内存不够会报错,所以建议大家不要用太大的数据验证。本代码注重的是算法逻辑,请知晓!
*/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char * myMallocCpy(char *s)
{
  int len = strlen(s) + 1;
  char *p = (char *)malloc(len);
  memset(p, 0, len);
  strcpy(p, s);
  return p;
}

char * myMallocLink(char *s1,char*s2)
{
  int len1 = strlen(s1);
  int len2 = strlen(s2);
  int len = len1 + len2+ 1;
 
  char *p = (char *)malloc(len);
  memset(p, 0, len);
  strcpy(p, s1);
  strcat(p, s2);
  return p;
}



char * zero(int n)
 {
  if (n == 0)
    return myMallocCpy("");
  if (n == 1)
    return myMallocCpy("0");
  char *s1 = zero(n / 2);
  char *s2 = zero(n / 2);
  char *s3 = zero(n % 2);
  char *s1Link = myMallocLink(s1, s2);
  char *s2Link = myMallocLink(s1Link, s3);
  return s2Link;
}

char* add(char* a, char* b)
{
  int lenOfA = strlen(a);
  int lenOfB = strlen(b);

  if (lenOfA <= 8 && lenOfB <= 8) { int x1 = atoi(a); int x2 = atoi(b); int sum = x1 + x2; int maxLen = lenOfA > lenOfB ? lenOfA : lenOfB;
    char*p = (char*)malloc(maxLen + 2);
    memset(p, 0, maxLen + 2);
    _itoa(sum, p,10);
    return p;
  }


  char * a1 = myMallocCpy("0");
  char * a2 = myMallocCpy(a);
 
  if (lenOfA > 8)
  {
    char tmp = a[lenOfA - 8];
    a[lenOfA - 8] = '\0';
    a1 = myMallocCpy(a);
    a[lenOfA - 8] = tmp;

    a2 = myMallocCpy(a + lenOfA - 8);
  }

  char * b1 = myMallocCpy("0");
  char * b2 = myMallocCpy(b);
  if (lenOfB > 8)
  {
    char tmp = b[lenOfB - 8];
    b[lenOfB - 8] = '\0';
    b1 = myMallocCpy(b);
    b[lenOfB - 8] = tmp;
    b2 = myMallocCpy(b + lenOfB - 8);

  }

  char* t = add(a2, b2);

  while (strlen(t)<8) { int tempLen = strlen(t); char *tt = (char*)malloc(tempLen + 1+1); memset(tt, 0, tempLen + 2); strcpy(tt + 1, t); t = tt; } if (strlen(t)>8)
  {
    char * padd1 = add(add(a1, b1), "1");
    int lenOdAdd1 = strlen(padd1);

    int lenOft = strlen(t);
    int lenSum = lenOdAdd1 + lenOft;

    char *pOk = (char*)malloc(lenSum);
    memset(pOk, 0, lenSum);

    strcpy(pOk, padd1);
    strcat(pOk, t + 1);

    return pOk;
  }

  char*padd2 = add(a1, b1);
  int lenOdAdd2 = strlen(padd2);

  int lenOft = strlen(t);

  int lenSum = lenOdAdd2 + lenOft + 1;
  char *pOk = (char*)malloc(lenSum);
  memset(pOk, 0, lenSum);

  strcpy(pOk, padd2);
  strcat(pOk, t);
  return pOk;
}

char* multi(char* a, char* b)
{
  int lena = strlen(a);
  int lenb = strlen(b);

  if (lena <= 4 && lenb <= 4) { int aInt = atoi(a); int bInt = atoi(b); int mul = aInt * bInt; int len = 0; int mulTmp = mul; while (mulTmp>0)
    {
      len++;
      mulTmp = mulTmp / 10;
    }

    char *p = (char*)malloc(len + 1);
    memset(p, 0, len + 1);

    _itoa(mul, p, 10);
    return p;
  }

  if (lena > 4)
  {
    int k = lena / 2;
    char aTemp = a[k];
    a[k] = '\0';
    char *pa1=myMallocCpy(a);
    a[k] = aTemp;
    char *pa2 = myMallocCpy(a+k);
   
    char *plh1 = multi(pa1, b);
    char *plh2 = zero(strlen(pa2));
    char*plh = myMallocLink(plh1, plh2);
    return add(plh, multi(pa2, b));
  }
  return multi(b, a);
}

void main()
{
  char *pl=myMallocLink("123", "567");
  char a[] = "1234567890";
  char b[] = "1234567890";


  printf("1234567890*1234567890 = ");
  printf("%s\n",multi(a, b));

/*  System.out.println(multi("1234567890987654321666",
    "1234567890123456789555"));

  System.out.println(new BigInteger("1234567890987654321666")
    .multiply(new BigInteger("1234567890123456789555")));*/

}


4. 提速

取球博弈和振兴中华等的递归解法有个弱点:

规模变大后,迅速超时…

解决方案:
1. 缓存子调用,把已经调用过的存在map中。
2. 不用递归,巧妙设计计算次序,使用数组存结果

【源代码】
【JAVA:于航】


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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//取球问题
public class A
{
  // n: 球数
  // return: true必赢
  static boolean f(int n){
    if(n==0) return true;
   
    if(n >= 1 && f(n-1)==false) return true;
    if(n >= 3 && f(n-3)==false) return true;
    if(n >= 7 && f(n-7)==false) return true;
    if(n >= 8 && f(n-8)==false) return true;    
    return false;
  }
 
  public static void main(String[] args){
    System.out.println(f(55));
  }
}

// 缓存法
import java.util.*;
public class B
{
  static Map map = new HashMap();
 
  // n: 球数
  // return: true必赢
  static boolean f(int n){
    if(map.get(n)!=null) return (Boolean)map.get(n);
   
    boolean t = false;
    if(n >= 1 && f(n-1)==false) t = true;
    if(n >= 3 && f(n-3)==false) t = true;
    if(n >= 7 && f(n-7)==false) t = true;
    if(n >= 8 && f(n-8)==false) t = true;
     
    map.put(n,t);
    return t;
  }
 
  public static void main(String[] args){
    map.put(0,true);
    System.out.println(f(1055));
  }
}

//振兴中华
public class AA
{
  static int f(int m, int n)
  {
    if(m==1 || n==1) return 1;
   
    return (f(m-1,n) + f(m,n-1)) % 10000;
  }
 
  public static void main(String[] args)
  {
    System.out.println(f(20,15));
    //System.out.println(f(3,2));
  }

}

public class BB
{
  static int f(int m, int n)
  {
    if(m==1 || n==1) return 1;  
    return (f(m-1,n) + f(m,n-1)) % 10000;
  }
 
  public static void main(String[] args)
  {
    int[][] a = new int[100][100];
   
    for(int i=1; i<100; i++){
      a[i][1] = 1;
      a[1][i] = 1;
    }
   
    for(int i=2; i<100; i++){
      for(int j=2; j<100; j++){
        a[i][j] = (a[i-1][j] + a[i][j-1]) % 10000;
      }
    }
    System.out.println(a[20][15]);
    System.out.println(f(20,15));
  }

}

【C:志愿者】


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
//取球问题
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int fff(int n)
{
  if (n == 0)
    return 1;

  if (n >= 1 && fff(n - 1) == 0)
    return 1;
  if (n >= 3 && fff(n - 3) == 0)
    return 1;
  if (n >= 7 && fff(n - 7) == 0)
    return 1;
  if (n >= 8 && fff(n - 8) == 0)
    return 1;

  return 0;
}

void main()
{
  printf("55 : %s\n",  fff(55) ? "true" : "false");
}

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
76
77
//取球问题
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct MyNode
{
  int n;
  int b;
  struct MyNode*pNext;
}MyNode;

MyNode *pHead = NULL;
MyNode *pTail = NULL;

void put(int n, int b)
{
  MyNode*pNode = (MyNode*)malloc(sizeof(MyNode));
  pNode->n = n;
  pNode->b = b;
  pNode->pNext = NULL;

  if (pHead == NULL)
  {
    pHead = pNode;
    pTail = pNode;
  }
  else
  {
    pTail->pNext = pNode;
    pTail = pNode;
  }
}

int get(int n)
{
  MyNode * pTemp = pHead;
  while (pTemp)
  {
    if (n==pTemp->n)
    {
      return pTemp->b;
    }
    pTemp = pTemp->pNext;
  }
  return -1;
}


// n: 球数
// return: true必赢
 int fa(int n)
 {
   if (get(n) != -1)
    return get(n);

  int t = 0;
  if (n >= 1 && fa(n - 1) == 0)
    t = 1;
  if (n >= 3 && fa(n - 3) == 0)
    t = 1;
  if (n >= 7 && fa(n - 7) == 0)
    t = 1;
  if (n >= 8 && fa(n - 8) == 0)
    t = 1;

  put(n, t);
  return t;
 }

void main()
{
  put(0, 1);
  int x=fa(1055);
  printf("%s", x ? "true" : "false");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//振兴中华
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int f5(int m, int n)
{
  if (m == 1 || n == 1)
    return 1;

  return (f5(m - 1, n) + f5(m, n - 1)) % 10000;
}

void main()
{

  printf("%d",f5(20, 15));

}

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
//振兴中华
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int fc(int m, int n)
{
  if (m == 1 || n == 1)
    return 1;
  return (fc(m - 1, n) + fc(m, n - 1)) % 10000;
}

void main()
{
  int a[100][100] = { 0 };

  for (int i = 1; i < 100; i++)
  {
    a[i][1] = 1;
    a[1][i] = 1;
  }

  for (int i = 2; i < 100; i++)
  {
    for (int j = 2; j < 100; j++)
    {
      a[i][j] = (a[i - 1][j] + a[i][j - 1]) % 10000;
    }
  }

  printf("%d\n", a[20][15]);
  printf("%d\n", fc(20, 15));
}


5. 城墙刷漆
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如图所示)
现需要把这些格子刷上保护漆。

你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)

比如:a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。

当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。
输入数据为一个正整数(不大于1000)
输出数据为一个正整数。

例如:
用户输入:
2
程序应该输出:
24

再例如:
用户输入:
3
程序应该输出:
96

再例如:
用户输入:
22
程序应该输出:
359635897

锦囊:

fb(n) 从边缘某格开始,到与它相邻的另一个边缘格子结束
fb(n) = fb(n-1) * 2

fa(n) 从某个边缘格子开始的所有情况
fa(n) = fb(n) + 2*fa(n-1) + 4 * fa(n-2)
最后走相邻边缘格 第1步走相邻边缘格 第2步走相邻边缘格

fk(i,n) 一共有n个格子,从中间的第i个格子为起点,任意结束
fk(i,n) = ( fb(i)*fa(n-i)*2 + fb(n-i+1)*fa(i-1)*2 ) * 2
先走左边再右边 先走右边再左边 有两个可能起点

总情况包含:
从某个边缘格开始的所有情况 4 * fa(i)
从中间某个格子开始的所有情况 i从2到n-1求和:fk(i,n)

【源代码】
【JAVA:于航】


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
76
77
78
79
80
81
82
83
84
85
86
87
88
public class A
{
  static long MM = 1000000007;
  // 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
  static long fb(int n)
  {
    if(n==1) return 1;
    return fb(n-1) * 2 % MM;
  }
 
  // 从某个边缘格子开始的所有情况
  static long fa(int n)
  {
    if(n==1) return 1;
    if(n==2) return 6;
    return (2 * fa(n-1) + 4 * fa(n-2) + fb(n)) % MM;
  }
 
  // 规模为n的问题之中间第i格
  static long fk(int i, int n)
  {
    //return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
    return (fb(i)*fa(n-i)*2 % MM + fb(n-i+1)*fa(i-1)*2 % MM) * 2 % MM;
  }
 
  static long f(int n)
  {
    if(n==1) return 2;
   
    long sum = fa(n) * 4 % MM;
    for(int i=2; i<n; i++){
      sum = (sum + fk(i,n)) % MM;
    }
    return sum;
  }
 
  public static void main(String[] args)
  {
    for(int i=1; i<30; i++){
      System.out.println(i + ": " + f(i));  
    }
  }
}

public class B
{
  static long M = 1000000007;
  // 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
  static long[] fb = new long[1000];
  // 从某个边缘格子开始的所有情况
  static long[] fa = new long[1000];
   
  // 规模为n的问题之中间第i格
  static long fk(int i, int n)
  {
    //return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
    return (fb[i]*fa[n-i]*2 % M + fb[n-i+1]*fa[i-1]*2 % M) * 2 % M;
  }
 
  static long f(int n)
  {
    if(n==1) return 2;
   
    long sum = fa[n] * 4 % M;
    for(int i=2; i<n; i++){
      sum = (sum + fk(i,n)) % M;
    }
    return sum;
  }
 
  public static void main(String[] args)
  {
    fb[1] = 1;
    for(int i=2; i<fb.length; i++){
      fb[i] = fb[i-1] * 2 % M;
    }
       
    fa[1] = 1;
    fa[2] = 6;
    for(int i=3; i<fa.length; i++){
      fa[i] = (2*fa[i-1] + 4 * fa[i-2] + fb[i]) % M;
    }
   
    for(int i=1; i<130; i++){
      System.out.println(i + ": " + f(i));  
    }
  }
}

【C:志愿者】


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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static long long MM = 1000000007;
// 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
long long fb6(int n)
{
  if (n == 1) return 1;
  return fb6(n - 1) * 2 % MM;
}

// 从某个边缘格子开始的所有情况
long long fa6(int n)
{
  if (n == 1) return 1;
  if (n == 2) return 6;
  return (2 * fa6(n - 1) + 4 * fa6(n - 2) + fb6(n)) % MM;
}

// 规模为n的问题之中间第i格
long long fk(int i, int n)
{
  //return fb6(i) * fa6(n-i) * 2 * 4 % MM; //相当于镜像互换了
  return (fb6(i)*fa6(n - i) * 2 % MM + fb6(n - i + 1)*fa6(i - 1) * 2 % MM) * 2 % MM;
}
long long f6(int n)
{
  if (n == 1) return 2;

  long long sum = fa6(n) * 4 % MM;
  for (int i = 2; i < n; i++){
    sum = (sum + fk(i, n)) % MM;
  }
  return sum;
}


void main()
{
  for (int i = 1; i < 30; i++)
  {
    printf("%d : %d\n", i, f6(i));
  }
}

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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static long long M = 1000000007;
  // 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
static long long fb[1000] = {0};
  // 从某个边缘格子开始的所有情况
static long long fa[1000] = { 0 };


  // 规模为n的问题之中间第i格
long long fk62(int i, int n)
{
  //return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
  return (fb[i] * fa[n - i] * 2 % M + fb[n - i + 1] * fa[i - 1] * 2 % M) * 2 % M;
}


long long f62(int n)
{
  if (n == 1) return 2;
  long long sum = fa[n] * 4 % M;
  for (int i = 2; i < n; i++)
  {
    sum = (sum + fk62(i, n)) % M;
  }
  return sum;
}

void main()
{
  fb[1] = 1;
  for (int i = 2; i < 1000; i++)
  {
    fb[i] = fb[i - 1] * 2 % M;
  }

  fa[1] = 1;
  fa[2] = 6;
  for (int i = 3; i < 1000; i++)
  {
    fa[i] = (2 * fa[i - 1] + 4 * fa[i - 2] + fb[i]) % M;
  }

  for (int i = 1; i < 130; i++)
  {
    printf("%d : %d\n",i,f62(i));
  }
}


6. 环形涂色

如上图,组成环形的格子需要涂3种颜色。
它们的编号分别是1~14
相邻的格子不能用相同的颜色。
涂色方案的数目是:24576

当格子数目为50的时候,求涂色方案总数。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class A
{
  /*
  static long f(int n){
    if(n==1) return 3;
    if(n==2) return 6;
    return 2 * f(n-2) + f(n-1);
  }
  */

 
  public static void main(String[] args){
    long[] f = new long[50+10];
    f[1] = 3;
    f[2] = 6;
    for(int i=3; i<=50; i++){
      f[i] = f[i-2] * 2 + f[i-1];
    }
   
    for(int i=3; i<=50; i++){
      System.out.println(i + ": " + f[i]);
    }
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 

void main()
{
  long long f[60] = { 0 };
  f[1] = 3;
  f[2] = 6;
  for (int i = 3; i <= 50; i++)
  {
    f[i] = f[i - 2] * 2 + f[i - 1];
  }

  for (int i = 3; i <= 30; i++)
  {
    printf("%d : %d\n",i,f[i]);
  }
}


如果您需要更多课程内容和讲解视频,请联系小蓝


Spread the word. Share this post!

Leave Comment

电子邮件地址不会被公开。 必填项已用*标注