分类：算法复习

参考答案：

#include <cstdio>
#include <cstring>
#include<stdlib.h>
int main()
{
  int n;
  int a[101][101];
  int sum;   //计数
  int i, j;
  scanf_s("%d", &n);
    sum = 0;
  int x = 0, y = n - 1;   // 代表 行列
  memset(a, 0, sizeof(a)); //将数组清零
  a[x][y] = ++sum;  //填入第一个数 ：1
  while (sum < n * n)
    {
      while (x + 1 < n && !a[x + 1][y])    // !a[x + 1][y] 代表这个区域未有数填入，区域依然为0
      {
        a[++x][y] = ++sum;
      }
      while (y - 1 >= 0 && !a[x][y - 1])
      {
        a[x][--y] = ++sum;
      }
      while (x - 1 >= 0 && !a[x - 1][y])
      {
        a[--x][y] = ++sum;
      }
      while (y + 1 < n && !a[x][y + 1])
      {
        a[x][++y] = ++sum;
      }
    }
  for (i = 0; i < n; i++)
    {
      for (j = 0; j < n; j++)
      {
        printf("%5d", a[i][j]);
      }
      printf("\n");
    }


  //system("pause");
  return 0;
}

解题思路：

//示例代码 C++

#include <cstdio>
#include <cmath>

long long n;

long long gcd(long long a,long long b)
//求最大公约数（用于约分和通分）
{
    if(!b)
    {
        return a;
    }
    return gcd(b,a%b);
}

int getlen(long long a)
//求一个数的位数（用于输出）
{
    return (int)(log(a)/log(10))+1;
}

struct frac
{
    long long z,m;

    int join(long long a,long long b)
    //构造一个分数，值为a/b
    {
        z=a;
        m=b;
        int y=gcd(z,m);
        z/=y;
        m/=y;
        //上面三步是约分
        return 0;
    }

    frac operator +=(const frac &other)
    //加法
    {
        long long pu=m*other.m/gcd(m,other.m);
        //pu是最简公分母
        z*=pu/m;
        long long otherz=other.z;
        otherz*=pu/other.m;
        m=pu;
        //上面4步是通分
        z+=otherz;
        //上面这一步是加法
        long long y=gcd(m,z);
        m/=y;
        z/=y;
        //上面三步是约分
        return *this;
    }

    int print()
    {
        long long pzh=z/m;
        long long pz=z-(z/m)*m;
        //pzh是带分数形式的整数部分，pz是带分数形式的分子
        if(pz)
        //如果有分子的话，输出分子
        {
            for(int i=1; i<=getlen(pzh); i++)
            {
                putchar(' ');
            }
            printf("%lld\n",pz);
        }
        printf("%lld",pzh);
        //输出整数部分
        if(pz)
        //如果有分数部分的话，输出分数线和分母
        {
            for(int i=1; i<=getlen(m); i++)
            {
                putchar('-');
            }
            putchar('\n');
            for(int i=1; i<=getlen(pzh); i++)
            {
                putchar(' ');
            }
            printf("%lld",m);
        }
        return 0;
    }
};

frac ans;

int main()
{
    scanf("%lld",&n);
    ans.join(0,1);
    //求sum(n/i)
    for(long long i=1; i<=n; i++)
    {
        frac x;
        x.join(n,i);
        ans+=x;
    }
    ans.print();
    putchar('\n');
    return 0;
}

参考答案：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long a, b, p;
long long gcd(long long a, long long b)      //求最大公约数,参与分数计算，使用long long型函数
{                                            //此GCD函数建议直接背下来，所有输出分数的题全部都要用到
  if (b == 0) return a;
  return gcd(b, a%b);
}

int main() {                                //题意为：从n种数中选出n个不同数的期望次数。
  int n, i; cin >> n; a = 1; b = 1;       //所以第一个球星抽到的概率是1，第n个是1/n。那么我们要从k个到k+1个球星的概率为（n-k）/n,所以期望为n/（n-k）。
  for (i = 2; i <= n; i++) {              //答案即为ANS=n(1/1+1/2+1/3+....1/n)
    a = a*i + b; b *= i;
    p = a; a /= gcd(a, b); b /= gcd(p, b);//计算 
  }
  a *= n;
  if (a%b == 0)cout << a / b;
  else {
    cout << a / b; a -= b*(a / b);
    cout << '(' << a / gcd(a, b) << '/' << b / gcd(a, b) << ')';//输出 
  }
  system("pause");
  return 0;
}

参考答案：

#include <bits/stdc++.h>  
#include <algorithm>
#define ll unsigned long long
using namespace std;

ll dp[1005][1005]; //定义数组大小   意义为抛n枚硬币，点数和为x的方案数

int gcd(int a, int b)      //自定义函数：欧几里得辗转相除法求最大公约数
{
  if (b == 0) return a;
  return gcd(b, a%b);
}
int main()
{
  ll n, k, i, j, m;
  cin >> n >> m;
  dp[0][0] = 1;
  for (i = 0; i < n; i++)  //外层循环：i从0到n-1表示抛第i枚硬币
  {
    for (j = 0; j <= i * 6; j++) //中层循环:j从0到i*6（骰子最大值为6，投两枚为2*6即12）
    {
      for (k = 1; k <= 6; k++) dp[i + 1][j + k] += dp[i][j]; //内层循环：k从1到6
    }
  }
  ll ans = 0, temp = 1;
  for (i = m; i <= 6 * n; i++) ans += dp[n][i];
  for (i = 0; i < n; i++) temp *= 6;
  if (ans%temp == 0)   //输出部分利用了最大公约数来输出标准分数，如果是整数则输出整数
  { 
    cout << ans / temp << endl; return 0;
  }
  
  ll t = gcd(ans, temp);
  cout << ans / t << "/" << temp / t << endl;
  system("pause");
  return 0;
}

参考答案：

#include<cstdio>
#include<cstring>
#include<cstdlib>
char a[1000];
int main()
 {
 unsigned int i, count = 0;   //定义无符号int值
   gets_s(a);
  for (i = 0; i <= strlen(a) - 1; i++) //计算字符长度
  if (a[i] >= '0'&&a[i] <= '9')
   count++;
  printf("%d", count);
  system("pause");
   return 0;
 }