算法刷题笔记二

前言

这篇文章的算法题全部来自PTA，笔试发现在线编程题自己太水，计划每周坚持刷些ACM题。

4-6 求单链表结点的阶乘和

本题要求实现一个函数，求单链表L结点的阶乘和。这里默认所有结点的值非负，且题目保证结果在int范围内。==>传送门

代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node *PtrToNode;
struct Node {
    int Data; /* 存储结点数据 */
    PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

int FactorialSum( List L );

int main()
{
    int N, i;
    List L, p;

    scanf("%d",&N);
    L = NULL;
    for (i=0; i < N; i++ ) {
        p = (List)malloc(sizeof(struct Node));
        scanf("%d",&p->Data);
        p->Next = L;  
        L = p;
    }
    printf("%d\n", FactorialSum(L));

    return 0;
}

int fac(int n) 
{
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;  
}

int FactorialSum( List L )
{
    List p = L;
    int sum = 0;
    while(p)
    {
        sum += fac(p->Data);
        p = p->Next;
    }
    return sum;
}

4-7 统计某类完全平方数

本题要求实现一个函数，判断任一给定整数N是否满足条件：它是完全平方数，又至少有两位数字相同，如144、676等。 ==>传送门

代码：

#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Median( ElementType A[], int N );

int main ()
{
    ElementType A[MAXN];
    int N, i;

    scanf("%d",&N);
    for ( i=0; i < N; i++ )
        scanf("%f",&A[i]);
    printf("%.2f\n", Median(A, N));

    return 0;
}

ElementType Median( ElementType A[], int N )
{
    int pos;
    ElementType temp;
    for (int i = 0; i < N / 2 + 1; i++)
    {
        pos = i;
        for (int j = i+1; j < N; j++)
        {
            if(A[pos] < A[j])
            {
                pos = j;
            }
        }
        if (i != pos)
        {
            temp = A[i];
            A[i] = A[pos];
            A[pos] = temp;
        }
    }
    return A[N/2];
} 

4-9 统计个位数字

本题要求实现一个函数，可统计任一整数中某个位数出现的次数。例如-21252中，2出现了3次，则该函数应该返回3。 ==>传送门

代码：

#include <stdio.h>
int Count_Digit( const int N, const int D );

int main()
{
    int N, D;         
    scanf("%d %d",&N,&D);
    printf("%d\n", Count_Digit(N, D));
    return 0;
}

int Count_Digit ( const int N, const int D )
{
    int n = N;
    if(N < 0) {
        n = -N;
    } 
    else if (N == 0 && D == N) 
    {
        return 1;
    }

    int times[10] = {0};
    while(n) 
    {
        times[n%10]++;
        n = n / 10;
    }
    return times[D];
}

4-10 阶乘计算升级版

本题要求实现一个打印非负整数阶乘的函数。 ==>传送门

代码：

#include <stdio.h>

void Print_Factorial ( const int N );

int main()
{
    int N;

    scanf("%d",&N);
    Print_Factorial(N);
    return 0;
}

int fac(int n) 
{
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;  
}

void Print_Factorial ( const int N )
{
    if (N < 0)
    {
        printf("Invalid input");
    }
    else
    {
        int result[5001] = {0}; // 保存结果的数组 

        int len = 1;        // 保存当前数组的长度 
        int carry_bit;          // 进位
        int temp;           

        result[1] = 1;      // 第一个计算时置为1 
        for (int i = 1; i <= N; i++)
        {
            // 按位乘,计算阶乘 
            carry_bit = 0;
            for (int j = 1; j <= len; j++)
            {
                temp = result[j] * i + carry_bit;
                result[j] = temp % 10;
                carry_bit = temp / 10;
            } 
            // 进位,构造下一轮的数组 
            while (carry_bit != 0)
            {
                len++;
                result[len] = carry_bit % 10;
                carry_bit = carry_bit / 10;
            }
        }
        for (int i = len; i >= 1; i--)
        {
            printf("%d", result[i]);
        }
        printf("\n");
    }
}

5-2 然后是几点

读入两个数字，第一个数字以这样的四位数字表示当前时间，第二个数字表示分钟数，计算当前时间经过那么多分钟后是几点，结果也表示为四位数字。 ==>传送门

代码：

import java.util.Scanner;

/**
 * Created by LuoWenqing on 2017/5/9.
 */
public class Main5_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int start, passed;
        int startHour, startMinute, totalMinute;
        int resultHour, resultMinute;

        while (sc.hasNext()) {
            start = sc.nextInt();
            passed = sc.nextInt();

            startHour = start / 100;
            startMinute = start % 100;
            totalMinute = startHour * 60 + startMinute;

            totalMinute += passed;

            if (totalMinute == 0) {
                resultHour = 0;
            } else {
                resultHour = totalMinute / 60;
            }

            resultMinute = totalMinute % 60;

            System.out.printf("%d%02d", resultHour, resultMinute);
        }
    }
}

声明：本站所有文章均为原创或翻译，遵循署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议，如需转载请确保您对该协议有足够了解，并附上作者名 (Tsukasa) 及原文地址