高精部分求助

P1255 数楼梯

luogu530225 @ 2022-01-25 16:16:09

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b,c;
    int d[700]={0};
    for(int i=0;i<=699;i++)d[i]=0;
    cin>>a>>b;
    int lena= a.length();
    int lenb= b.length();
    int len=max(lena,lenb);
    for(int i=len-1;i>=0;i--){
        if(a[i]>='0'&&a[i]<=('9'+9)&&b[i]>='0'&&b[i]<=('9'+9))c[i]=a[i]+b[i]-'0';
        else if(a[i]>='0'&&a[i]<=('9'+9))c[i]=a[i];
        else c[i]=b[i];
        if(d[i]==1){
        c[i]+=1;
        }
        if(c[i]>'9'){
            c[i]-=10;
            d[i-1]=1;
        }
    }
    if(c[len]=='1'){
        for(int i=0;i<=len;i++){
            cout<<c[i];
        }
    }else for(int i=0;i<=len-1;i++){
        cout<<c[i];
    }
    return 0;
} 

by AFewSuns @ 2022-01-25 16:26:05

主页双帖,紫衫请


by EC75 @ 2022-01-25 16:46:02

@贾旭尧666 用Python

i=int(input())
a=1
b=1
c=1
x=3
mod=1000000009
while x<=i+1:
    c=a+b
    a=b
    b=c
    x=x+1
if i==0:
    print(0)
else:
    print(c)

by luogu530225 @ 2022-01-25 17:13:20

@AFewSuns ??


by Mandel520 @ 2022-01-25 20:20:02

写复杂了, 高精部分这样实现就可以了

#include<stdio.h>

int steps[5005][5005];
int n;

int main(){
    scanf("%d", &n);
    steps[1][1] = 1; //走上第一层有1种方案
    steps[2][1] = 2; //走上第二层有2种方案

    for (int i = 3; i <= n; i++){//高精度加法
        for (int j = 1; j <= 5000; j++){
            steps[i][j] += steps[i - 1][j] + steps[i - 2][j];//这一位的值是前面两行这一位的值之和(斐波那契)
            steps[i][j] += steps[i][j - 1] / 10;  //处理进位
            steps[i][j - 1] %= 10;  //处理进位
        }
    }

    int ok = 0; 
    for (int i = 5000; i >= 1; i--) { //输出第n层的总方案数
        if (steps[n][i]) ok = 1;
        if (ok) printf("%d", steps[n][i]);
    }
    if (ok == 0) printf("0");
    puts("");

    return 0;
}

by juxiaodong @ 2022-02-05 22:39:09

@Jeremy_Mandel 当需要输出的数中间有0时,最后一个for循环是怎样判断是否输出0的?或者你能不能再解释解释从int ok;到末尾的算法实现?我还是不太理解怎样输出的


by Mandel520 @ 2022-02-06 12:03:41

@jxdasdfghjkl

例如, 存在数组steps[n]中的数是:

[0, 1, 0, 3, 0, 0]

最后一个for循环从后往前输出时:

首先遇到0, 此时ok = 0, 不输出

然后遇到0, 此时ok = 0, 不输出

然后遇到3, 因此ok变成1, 输出3

然后遇到0, 此时ok = 1, 输出0

然后遇到1, 此时ok = 1, 输出1

然后遇到0, 此时ok = 1, 输出0

因此最后输出结果为3010

总结: 一旦遇到第一个不为0的数, 后面的数都会输出, 所以数字中间的0也会输出


by juxiaodong @ 2022-02-06 19:26:12

@Jeremy_Mandel 明白了,谢谢


by Crybaby_ @ 2022-02-27 16:30:37

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#define MAXN 105
typedef long long ll;
using namespace std;
const int N = 101;

int step[5001][5001];
int main() {
    int n;
    scanf("%d", &n);
    step[1][1] = 1;
    step[1][0] = 1;
    step[2][1] = 2;
    step[2][0] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j <= step[i - 1][0]; j++) {
            step[i][j + 1] += (step[i - 1][j] + step[i - 2][j] + step[i][j]) / 10;
            step[i][j] = (step[i - 1][j] + step[i - 2][j] + step[i][j]) % 10;
        }
        if (step[i][step[i - 1][0] + 1] > 0) {
            step[i][0] = step[i - 1][0] + 1;
        } else {
            step[i][0] = step[i - 1][0];
        }
    }
    for (int i = step[n][0]; i > 0; i--) {
        printf("%d", step[n][i]);
    }
    return 0;
}

|