- 1Java类的加载过程_java类加载过程
- 2Uniapp Vue3 基础到实战 教学视频_uniapp 地图实战 vue3
- 3html5 多点触控 缩放,WebBrowser禁用触摸缩放
- 4Interfacing an SPI ADC (MCP3008) chip to the Raspberry Pi using C++ (spidev)_mcp3008 python
- 5鸿蒙手机发布失败,华为鸿蒙能不能成功？先看看微软，它当年是怎么失败的
- 6鸿蒙HarmonyOS开发环境搭建_harmonyos 键值对数据结构有哪些
- 7关于 Caused by: org.a.a.e: Subscriber class com.xxx.xxx.activity.MainActivity and its super class_subscriber class link.shenxian.main.activity.maina
- 8[动态规划]---part2
- 9Python----Python安装包出现Failed building wheel for xxx的问题解决办法_failed building wheel for dm-tree
- 10utf-8编码，转换为中文 JavaScript_java代码utf-8编码转换中文
关于Java编程实现n个小球涂色的问题_有n个小球排成一行,现在要对每个小球染一种颜色,一共有c 种颜色可供使用。若要求
赞
踩
把这n个小球排成一线，然后给这n个小球涂色，假设共有三种颜料，要求相邻的小球不能同色，且第一个小球和最后一个小球不能同色，问共有多少种涂色方式，请给出最终结果的表达式。
解决这个问题的其中一个方法是用树的思想，假设三种颜色分别为1,2,3，第一个小球颜色为1，则如下面的图片所示：
（为叙述方便，不妨设f1(n)=f(n),f2(n)=g(n)）
根据递推式g(n)=2f(n-1)-g(n-1),可以得出g(n)的表达式
所以我们易知所有的涂色种数为g(n)*3种。
我们需要编程来实现当n（1<=n<=10000）时，总共的涂色种数，由于结果过大，故只需输出结果与1000000007的余数即可，但是本人在编程时遇到以下问题
（1）.中间计算过程所需数据的位数过大，发生数据溢出。
这个问题可以用BigInteger类进行解决。但是用这个类的话需要多次压栈，所以运算效率很低，尽管如此，我也必须用这个类进行处理。
（2）.既然是递推式，那么需要用递归减少代码量，但是如果用递归的话，更需要多次压栈，又一次大大的降低了运算效率。结果更可怕，发生了堆栈溢出。
这个问题我用了把递归拆开的方法，呵呵，虽然挺笨，但是结果却解决了堆栈溢出的问题。
综上所述我的代码如下：
import java.math.BigInteger;
public class Main {
public static void main(String args[]){
Scanner reader=new Scanner(System.in);
BigInteger h=new BigInteger("3");
BigInteger p=new BigInteger("1000000007");
int m;
BigInteger result;
m=reader.nextInt();
long n[]=new long[m];
for(int i=0;i<m;i++)
n[i]=reader.nextInt();
for(int i=0;i<m;i++){
result=notSame(n[i]).multiply(h).remainder(p);
System.out.println(result);
}
}
static BigInteger numberAll(long x){
BigInteger a=new BigInteger("2");
BigInteger result=new BigInteger("1");
for(int i=0;i<x-1;i++){
result=result.multiply(a);
}
return result;
}
static BigInteger notSame(long x){
BigInteger t=new BigInteger("2");
BigInteger p=new BigInteger("2");
for(int i=3;i<=x;i++){
p=t.multiply(numberAll(i-1)).subtract(p);
}
return p;
}
}
这是至今为止我能想到的唯一解决方案，我觉得应该有更好的解决方案，其中包括算法的选择，大数据的处理方式，以及递推堆栈溢出的解决方案。注意，必须保证测试时n能取到10000才行。毕竟这样测试虽然能出结果，但总共花了30秒才能运行出结果，运行效率太慢了。这个问题有待解决......
接上，经过我的虚心请教和 勇于实践，终于在一定程度上解决了这个效率问题，毕竟一个程序30秒出结果却是有些夸张。
具体算法如下：
g(n)=2*f(n-1)-g(n-1)
=2*f(n-1)-(2*f(n-2)-g(n-2))
=2*(f(n-1)-f(n-2))+g(n-2)
=2*(f(n-1)-f(n-2))+(2*f(n-3)-g(n-3))
=2*(f(n-1)-f(n-2)+f(n-3))-g(n-3)
=2*(f(n-1)-f(n-2)+f(n-3)-f(n-4))+g(n-4)
=...............
=2*(f(n-1)-f(n-2)+f(n-3)-f(n-4)+f(n-5)-f(n-6)+...(+/-)f(2))(-/+)g(2)
令s= f(n-1)-f(n-2)+f(n-3)-f(n-4)+f(n-5)-f(n-6)+...(+/-)f(2)
则g(n)=2*s(-/+)g(2)
因此，只需设计一个函数实现s即可
当n 为奇数时，则1~n为n个数即奇数个数，则2~n-1为奇数个数，此时，f(2)与f(n-1)同号,而g(2)与f(2)异号
s= f(n-1)-f(n-2)+f(n-3)-f(n-4)+f(n-5)-f(n-6)+...+f(2) ; g(n)=2*s-g(2)
当n 为偶数时，则1~n为n个数即偶数个数，则2~n-1为偶数个数，此时，f(2)与f(n-1)异号,而g(2)与f(2)异号
s= f(n-1)-f(n-2)+f(n-3)-f(n-4)+f(n-5)-f(n-6)+...-f(2) ; g(n)=2*s+g(2)
针对此算法，我的代码如下：
import java.util.Scanner;
import java.math.BigInteger;
static BigInteger n=new BigInteger("-1");
public static void main(String args[]){
Scanner reader=new Scanner(System.in);
BigInteger h=new BigInteger("3");
BigInteger p=new BigInteger("1000000007");
int m;
BigInteger result;
m=reader.nextInt();
long n[]=new long[m];
for(int i=0;i<m;i++)
n[i]=reader.nextInt();
for(int i=0;i<m;i++){
result=all(n[i]).add(notSame2(n[i]));
result=result.multiply(h);
result=result.remainder(p);
System.out.println(result.abs());
}
}
static BigInteger numberAll(long x){
BigInteger a=new BigInteger("2");
BigInteger result=new BigInteger("1");
for(int i=0;i<x-1;i++){
result=result.multiply(a);
}
return result;
}
static BigInteger all(long x){
BigInteger r=n;
BigInteger t;
BigInteger s=new BigInteger("0");
if(x%2==0){
r=r.multiply(n);
}
for(int i=3;i<=x-1;i++){
t=r.multiply(numberAll(i));
s=s.add(t);
r=r.multiply(n);
}
s=s.multiply(new BigInteger("2"));
return s;
}
static BigInteger notSame2(long x){
if(x%2==0)
return new BigInteger("-2");
else
return new BigInteger("2");
}
}
这次运行出结果共化了28秒，哈哈，少了两秒......事实证明，结果不如预期，但是也算是一个迈进......
接上，我发现一个算法如果人算的越多，计算计算的就越少，为什么这么说呢？
由于g(n)=2*s(+/-)g(2)
当n 为奇数时，则1~n为n个数即奇数个数，则2~n-1为奇数个数，此时，f(2)与f(n-1)同号,而g(2)与f(2)异号
s= f(n-1)-f(n-2)+f(n-3)-f(n-4)+f(n-5)-f(n-6)+...+f(2) ; g(n)=2*s-g(2)
当n 为偶数时，则1~n为n个数即偶数个数，则2~n-1为偶数个数，此时，f(2)与f(n-1)异号,而g(2)与f(2)异号
s= f(n-1)-f(n-2)+f(n-3)-f(n-4)+f(n-5)-f(n-6)+...-f(2) ; g(n)=2*s+g(2)
f(n)=2^(n-1),所以我们能进一步算出s的表达式：
前提：f(n)-f(n-1)=2^(n-1)-2^(n-2)=2^(n-2)
（1）当n 为奇数时，则1~n为n个数即奇数个数，则2~n-1为奇数个数，所以，3~n-1则为偶数个，此时：
s=(f(n-1)-f(n-2))+(f(n-3)-f(n-4))+...+(f(4)-f(3))+f(2)
=(2^(n-2)-2^(n-3))+(2^(n-3)-2^(n-4))+...+(2^4-2^3)+2^1
=(2^(n-3)+2^(n-5)+...+2^3)+2
=[等比数列求和]+2
易计算得：此等比数列，共(n-3)/2项，首项为2^3=8,公比为2^2=4,则,
s=(2^n+4)/3
（2）当n 为偶数时，则1~n为n个数即偶数个数，则2~n-1为偶数个数，此时：
s=(f(n-1)-f(n-2))+(f(n-3)-f(n-4))+...+(f(3)-f(2))
=(2^(n-2)-2^(n-3))+(2^(n-3)-2^(n-4))+...+(2^3-2^2)
=2^(n-3)+2^(n-5)+...+2^2
=[等比数列求和]
易计算得：此等比数列，共(n-2)/2项，首项为2^2=4,公比为2^2=4,则,
s=(2^n-4)/3
综上所述，易得，总共的方案种数：
（1）当n为奇数时，为2^n-2
（2）当n为偶数时，为2^n+2
这样算出最终结果后，在进行编程实现就容易多了，而且效率也大大提高了（我眼泪都快出来了）......
针对此算法，我的代码如下：
import java.util.Scanner;
import java.math.BigInteger;
public static void main(String args[]){
Scanner reader=new Scanner(System.in);
BigInteger h=new BigInteger("2");
BigInteger p=new BigInteger("1000000007");
int m;
BigInteger result;
m=reader.nextInt();
long n[]=new long[m];
for(int i=0;i<m;i++)
n[i]=reader.nextInt();
long resul;
for(int i=0;i<m;i++){
if(n[i]%2==1)
result=fang(n[i]).subtract(h);
else
result=fang(n[i]).add(h);
result=result.remainder(p);
System.out.println(result);
}
}
static BigInteger fang(long x){
BigInteger result=new BigInteger("1");
BigInteger t=new BigInteger("2");
for(int i=0;i<x;i++)
result=result.multiply(t);
return result;
}
}
不知道为什么，一种被坑了的感觉特别强烈，但是这种方法确实是快啊，用了不到100毫秒就出结果了......效率提高了不止数十倍。
接上：问题到这里算解决了，呵呵，其实远远不够，其实问题的原版是n最高能测试到n=10^19不出问题才行（我要哭了）
我不得不说，我黔驴技穷了......
算了，我不得不请教了我们宿舍的某位fudq学长，他给出了一个C++算法，传说中他不会java，说使用了什么矩阵倍增的方法
我晕，我完全看不懂啊......
我把代码贴出来，大家看看，如果有弄明白这算法什么意思的一定要通知我哈：
//特别声明，这个算法原创属于付德强学长，任何非学术研究方面的引用、转载请务必经过他本人同意
#include<iostream>
using namespace std;
#define LL __int64
const int N=5;
const LL M=1000000007;
#define MEM(a) (memset((a),0,sizeof(a)))
struct Matrix{
LL v[N][N];
};
{
Matrix c;
MEM(c.v);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
c.v[i][j]=(c.v[i][j]+m1.v[i][k]*m2.v[k][j])%pri;
return c;
}
{
Matrix c,x=A;
MEM(c.v);
for(int i=0;i<N;i++)
c.v[i][i]=1;
while(n >= 1)
{
if(n & 1)
c=Mat_mul(c,x,pri);
n>>=1;
x=Mat_mul(x,x,pri);
}
return c;
}
void init(Matrix &tmp)
{
MEM(tmp.v);
tmp.v[0][0]=1;tmp.v[0][1]=1;tmp.v[1][0]=2;tmp.v[1][1]=0;
}
{
Matrix tmp,ans;
init(tmp);
ans=Mpow(tmp,n-3,M);
LL res=((6*ans.v[0][0])%M+(6*ans.v[1][0])%M)%M;
printf("%I64d\n",res);
}
{ int T;
scanf("%d",&T);
while(T--)
{
scanf("%I64d",&n);
if(n == 1)
printf("3\n");
else if(n == 2)
printf("6\n");
else if(n == 3)
printf("6\n");
else
solve();
}
return 0;
}
我感觉世界太大了，有很多你想想不到的强大的人类存在，要想不落后与他们，就必须得玩命的学习学习在学习才行。昨天某把刀跟我说了一堆话，让我也有了些思考，我们现在比不上人家，这是肯定的。来林大这一年，我发现当你在糊弄时间的时候，别人关于算法每天都要进行一个小时的特训，长此以往，怎么可能是人家的对手呢。所以我觉得一切都是借口，我们只有努力努力在努力才行，相信终有一天，我们能走出自己内心的桎梏，走向那一片更广阔的蓝天。我不会放弃，尽管你说了，尽管你把扁的我看的更扁了，尽管你说的确实都是事实，但是，奋力一搏总比直接放弃要好哈哈......让暴风雨来的更猛烈些吧！！
