一个题目(据说又是一个面试题):
三个数的乘法:a*b*c,共有两种结合方式:(a*b)*c,a*(b*c)
四个数的乘法:a*b*c*d,共有五种结合方式:((a*b)*c)*c, (a*(b*c))*d, a*((b*c)*d), a*(b*(c*d)), (a*b)*(c*d)
写一个函数,参数是乘数的个数,返回值是用乘法结合律后可能的结合方式总数。
(链接:http://topic.csdn.net/u/20080626/13/4efca1a4-8534-44fd-ae87-f65463e7cb93.html)
递归方法没错:
f[n]=sigma(k=1:n, f[k]*f[n-k]);
绞尽脑汁想通项式,实在无能为力。
一开始想到的倒不是递归,而是Polish Notation(很基础的算法,用这个方法能够很方便作出24点枚举求算),以至于一时想不出来解法。但Polish的确有可能是一个解决之道:
一、将a,b,c,d...顺序排好。
二、第一个乘号最早只能处于b和c之间。假设这个位置记为P
0,于是全部位置为P
0到P
n-2。其中n为操作数个数。
三、乘号配置的规则是到任何一个位置的乘号总数少于此前所有操作数总数。
下图表示乘号位置选择演化图(到n=3+2=5):
0: 2
0 1
1: 3 2
0 1 2 0 1
2: 4 3 2 3 2
0 1 2 3 0 1 2 0 1 0 1 2 0 1
3: 5 4 3 2 4 3 2 3 2 4 3 2 3 2
...
其中含行号行表示对应状态可选情形数,其下方为对应的各情形和达致的新状态。例如0: 2表示P
0位置共有两种可选状态,分别为采用0或1个乘号。
每一行的规律是,最大数为n+2,最小数为2。其中数x的个数是上一行max(2,x-1)到其最大数的总个数。
下表表示n从0到4,各数的个数。例如对于n=1,共有1个2和1个3,而总情形数是5。
n
|
|
2
|
3
|
4
|
5
|
6
|
总数
|
0
|
0
|
1
|
|
|
|
|
2
|
1
|
0
|
1
|
1
|
|
|
|
5
|
2
|
0
|
2
|
2
|
1
|
|
|
14
|
3
|
0
|
5
|
5
|
3
|
1
|
|
42
|
4
|
0
|
14
|
14
|
9
|
4
|
1
|
132
|
...
|
... |
... |
... |
... |
... |
... |
... |
该表的规律是任何一个非0非1项是其左上数和右侧数的和。
这个表有个容易发现的性质,最右侧总数即最左侧非零列的一个提前,这个性质不难证明(略)。
于是最左一列数列就是题目的最终所求。
我目前仍未能给出其通项。(我考察了每个斜线,斜线上的数列是一个n+2次数列)。而所求数列由这个数列族的首项组成,这个首项应当不足以形成高次幂运算(例如记得曾讨论过的Fibonacci和它的变种会形成这种局面,以至使得通项对于优化计算几乎没有任何现实意义),其关键在于系数。前三个数列的通项分别为:1, k, (1/2)*k^2 + (3/2)*k。或许是有些规律,如果有哪位能够找出规律,笔者有兴趣求教。
但即使这样,这个讨论对优化计算也有明显作用:计算f[n],只要开一个长度n左右的数列,然后在这个数列上依照表格提示的规律进行多次加法运算,代码如下:
(遗憾的是,用乘法递推由于循环次数减半因素,和这个加法版本不相上下,甚至性能略微超出。如果用普通的递归则由于多次重复计算性能损失严重)
#include <stdio.h>
#include <stdlib.h>
int nummultasso2(int n)
{
int i, j, r;
int *a = 0;
if (n < 3)
{
return 1;
}
a = (int *)malloc(sizeof(int)*n);
for (i = 2; i < n; i++)
{
a[i] = i;
}
for (i = 3; i < n; i++)
{
for (j = i; j < n; j++)
{
a[j] += a[j-1];
}
}
r = a[n-1];
free(a);
return r;
}
int nummultasso(int n)
{
int i, j, m;
int r = 0;
int *a = 0;
if (n < 3)
{
return 1;
}
a = (int *)malloc(sizeof(int)*n);
a--;
a[1] = a[2] = 1;
for (i = 3; i <= n; i++)
{
a[i] = 0;
m = (i+1)/2;
for (j = 1; j < m; j++)
{
a[i] += a[j] * a[i-j] * 2;
}
if (i % 2 == 0)
{
a[i] += a[m] * a[m];
}
}
r = a[n];
a++;
free(a);
return r;
}
int main(void)
{
int i;
printf("version 1:/n");
for (i = 1; i < 21; i++)
{
printf("f[%d] = %d/n", i, nummultasso(i));
}
printf("version 2:/n");
for (i = 1; i < 21; i++)
{
printf("f[%d] = %d/n", i, nummultasso2(i));
}
}
分享到:
相关推荐
世界500强面试题 25年面试官首次揭秘——世界500强面试题(精彩选载)
2024——07_大数据面试题干货盘点.pdf2024——07_大数据面试题干货盘点.pdf2024——07_大数据面试题干货盘点.pdf2024——07_大数据面试题干货盘点.pdf2024——07_大数据面试题干货盘点.pdf2024——07_大数据面试题...
2024秋招and春招——悦能智能科技面试题.txt2024秋招and春招——悦能智能科技面试题.txt2024秋招and春招——悦能智能科技面试题.txt2024秋招and春招——悦能智能科技面试题.txt2024秋招and春招——悦能智能科技面试...
5 年面试官首次揭秘——世界 500 强面试题
计算机网络——计算机网络常见面试题总结.pdf
搜狗往期面试题总结
鹅厂往期面试题的总结
2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端...
世界500强面试题——让你在面试时更有自信!
2022前端面试系列——Vue面试题.pdf
百度大厂往期面试题汇总(或许不全)
c++面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试...
2024年秋招and春招——中威面试题.pdf2024年秋招and春招——中威面试题.pdf2024年秋招and春招——中威面试题.pdf2024年秋招and春招——中威面试题.pdf2024年秋招and春招——中威面试题.pdf2024年秋招and春招——中威...
Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案
01 java面试——北京-百度-Java中级.pdf 02 java面试——北京-京东-Java中级.pdf 03 java面试——广州-唯品会-Java大数据开发工程师.pdf 04 java面试——杭州-阿里云-Java中级.pdf 05 java面试——杭州-蚂蚁金服-...
Java面试题——先留着,以后用得着 用最有效率的方法算出2乘以8等於几? 答案:2 << 3
面试题解惑系列(十)——话说多线程面试题解惑系列(十)——话说多线程面试题解惑系列(十)——话说多线程
JavaOOP面试题 Java集合/泛型面试题 Java异常面试题 Java中的IO与NIO面试题 Java反射面试题 Java序列化面试题 Java注解面试题 多线程&并发面试题 JVM面试题 Mysql面试题 Redis面试题 Memcached面试题 MongoDB面试题 ...
这是java程序员面试题的总结,非常经典,来自于河南省863软件孵化器有限公司。对于有一定技术,面试却总是失败的朋友很有帮助。
Java陷阱一箩筐——面试题集 Java陷阱一箩筐——面试题集 Java陷阱一箩筐——面试题集 Java陷阱一箩筐——面试题集