荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: dynamic (dynamic), 信区: Program
标 题: 贴答案了
发信站: 荔园晨风BBS站 (2006年01月03日22:19:46 星期二), 站内信件
一、简单题
这种问题，会的就不屑答，不会的就baidu一下. 这里略过了, sorry..
二、
////////////////////////////////////////////////////////////////////////
/////////////////
6. 阶乘, code如下:
# include <stdio.h>
# include <math.h>
# define MAX 100000
int res[MAX]; //储存结果，每一个int保留4位整数，所以n!在4*MAX位以内时，
算法保证正确.
int max_n() //计算当内存是MAX时，可计算的n是多少.
{
/*
n!的位数 = log10(n!) 取整后加1. 故
n!的位数 = log10(1)+log10(2)+...+log10(n)取整加1.
当然，也可以用Stirling逼近公式来计算，这样快好多，
不过考虑到贵公司的工程师数学水平有限，可能看不懂，
所以还是用这个方法来计算就算了.
*/
double ans=0;
int i;
for(i=1;;i++) {
ans+=log10(i);
if(floor(ans)+1>=4*MAX) break;
}
return i-1;
}
void Factor(int n)
{
int i,carry,j,digit;
if( n>max_n() || n<0) {
printf("n is too large! or n is negative!\n");
return ;
// max_n()可以先做预处理.
// 当然，也可以用max_n()中的方法，计算出n!的位数后再动态开辟内
存
，不过
我不喜欢这样. ^_^
}
res[0]=1;
digit=0;
for(i=1;i<=n;i++) {
carry=0;
for(j=0;j<=digit;j++) {
res[j]=res[j]*i+carry;
carry=res[j]/10000;
res[j]%=10000;
}
while(carry) digit++,res[digit]=carry%10000,carry/=10000;
}
printf("%d",res[digit]);
for(i=digit-1;i>=0;i--) printf("%.4d",res[i]);
printf("\n");
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF) Factor(n);
return 0;
}
////////////////////////////////////////////////////////////////////////
/////////////////////
7. 求F_n
//递归版本..不考虑高精度大数了，反正这是体力活，以免大家看得辛苦.
# include <stdio.h>
# include <string.h>
# define MAX 1000000
long long F[MAX];
bool haveBeenCal[MAX]; //递归防止重复计算.
long long Cal(int n)
{
if(haveBeenCal[n]) return F[n];
haveBeenCal[n]=1;
return F[n]=Cal(n-1)-Cal(n-3);
}
int main()
{
int n;
memset(haveBeenCal,0,sizeof(haveBeenCal));
haveBeenCal[0]=haveBeenCal[1]=haveBeenCal[2]=1;
F[0]=0,F[1]=1,F[2]=2;
while(scanf("%d",&n)!=EOF) {
if(n<0||n>=MAX) printf("inavailabe n\n");
printf("%lld\n",Cal(n));
}
return 0;
}
//非递归版本
# include <stdio.h>
# define MAX 100000
int F[MAX];
int main()
{
int n,i,max;
F[0]=0,F[1]=1,F[2]=2;
max=2;
while(scanf("%d",&n)!=EOF) {
if(n<=max) {
printf("%d\n",F[n]);
continue;
}
for(i=max+1;i<=n;i++) F[i]=F[i-1]-F[i-3];
max=n;
printf("%d\n",F[n]);
}
return 0;
}
注: 对于这一题，我们还有另一个算法，对于一个n,不用一步一步地推n次，只要
推lg(n)次就可以了.
这是因为
_ _ - - - -
| F[n] | | 1 0 -1 | | F[n-1] |
| F[n-1] | = | 0 0 0 | *| F[n-2] |
| F[n-2] | | 0 1 0 | | F[n-3] |
- - - - - -
再推下去，得:
_ _ - - ^(n-2) - -
| F[n] | | 1 0 -1 | | F[2] |
| F[n-1] | = | 0 0 0 | * | F[1] |
| F[n-2] | | 0 1 0 | | F[0] |
- - - - - -
于是，问题就转化成如何求一个矩阵的n次方了，用分治的思想就可以做到lg(n)咯
，好简单，这里略，
可以参考素数判写的Miller-Rabin算法..kaka.
////////////////////////////////////////////////////////////////////////
/////////////
8. 链表排序
//直接修改一下Mergesort就可以了,nlogn
# include <stdio.h>
typedef struct _node_t{
int a;
struct _node_t* next;
}node_t;
node_t* Mergesort(node_t* L,int count) //链表头及要链表元数个数
{
if(count==1) return L;
int count1=count/2;
int count2=count-count1;
node_t* p=L;
int i;
for(i=0;i<count1;i++) p=p->next;
node_t* h1=Mergesort(L,count1);
node_t* h2=Mergesort(p,count2);
int t1=0,t2=0;
node_t *head=NULL,*cur;
while(t1<count1||t2<count2) {
if(t1<count1&&t2<count2) {
if(h1->a < h2->a) p=h1,h1=h1->next,t1++;
else p=h2,h2=h2->next,t2++;
}
else if(t1<count1) p=h1,h1=h1->next,t1++;
else p=h2,h2=h2->next,t2++;
if(head==NULL) head=cur=p;
else {
cur->next=p;
cur=p;
}
}
return head;
}
void sort(node_t* &a)
{
int count=0;
node_t* p=a;
while(a) {
count++;
a=a->next;
}
a=Mergesort(p,count);
p=a;
int i;
for(i=0;i<count-1;i++) p=p->next;
p->next=NULL;
}
void input(node_t* &a)
{
a=NULL;
int n;
node_t* p;
while(scanf("%d",&n)!=EOF) {
node_t* s= new node_t;
s->a=n;
if(a==NULL) a=p=s;
else p->next=s;
p=s;
p->next=NULL;
}
}
void output(node_t* a)
{
while(a) {
printf("%d ",a->a);
a=a->next;
}
printf("\n");
}
int main()
{
node_t* a;
//freopen("test.in","r",stdin);
input(a);//屏幕输入时输一串数字，然后按enter再按ctrl+z结束
sort(a);
output(a);
return 0;
}
////////////////////////////////////////////////////////////////////////
/
三、
9、集合合并
(1) 主要思路
关键就是两步:
1. 确定那些集合要合成一堆.
2. 如何合并一堆集合.
(2) 算法
1. 每个元素对应一个桶，装含有该元素的集合的编号.
如例子中:
{aaa}: 1
{bbb}: 1 2
{ccc}: 1
{ddd}: 2 5
{eee}: 3
{fff}: 3
{ggg}: 4
{hhh}: 5
这一步须时(所有集合中元素个数的总和).
2. 然后用并查集，每个桶中相邻的两个集合就要合并.
如上例，集合1,2,5要合并，其它独立.
这步须时, 总元素个数*a(总元素个数)
其中a(n)是Ackman函数的反函数，一般<=4,所以也大约地关于总元素个数成线
性.
3. 合并集合
例如，现在要分别合并集合的编号为1,2,5及集合编号为3,4,6的集合.
那么，我们就把集合1,2,5中含有的元素都标记为1.
再把3,4,6中含的元素都标记为2.
然后把所有元素扫一次，按标号分类就可以了.
复杂度,O(总元素个数).
综上,复杂度大约是O(总元素个数).
当然,这里不包括由给每个元素编号的复杂度,其实复杂度不高的吧,就是用最弱智
的方法就可以做到
不同元素的个数*log(不同元素的个数).
(3)改进
有比上面的算法快的话你通知一声我,谢谢.
: 【 在
: dynamic (dynamic) 的大作中提到: 】: 这是第一大题的
: //ps,baidu好白痴，它的网页做成不可以copy题目，但系查看一下源文件就copy了，
: //呵呵.
: 1. 请列举你所知道的Linux或者Windows进程间通迅的方式（请选择一种平台回答
: ，至少回答6个或以上）?
: 2. 实现一个TCP端口监听服务进程通常需要使用那些socket函数,并请描述这些函
: 数的作用？（至少回答6个或以上）
: 3. 将基于多进程模型的程序移植为基于多线程模型的程序，通常需要如何修改调
: 整程序（解决那些问题）？
: 4. 什么是C/C++的模板（template）编程, 有什么好处？
: .................（以下省略）
--
同人见面：how do u do !
____(```\一糸one .-'""""`-.二糸tow /```)____
笑 (____ \_____ / (O O) \ _____/ ____) 十 ┌————┐
一 (____ ( ) ) ____) 年 │笑脸小子│
笑 (____ _______\ \____/ /_____ __ ____) 少 └————┘
(______/ 我糸I `-.____.-' 你糸U \______)
※ 修改:·bakey 於 01月03日22:22:48 修改本文·[FROM: 210.21.224.233]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.21.224.233]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店