1008 数组元素循环右移问题

一个数组AAA中存有NNN>0>0>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移MMM≥0\ge 00)个位置,即将AAA中的数据由(A0A1⋯AN−1A_0 A_1 \cdots A_{N-1}A0A1AN1)变换为(AN−M⋯AN−1A0A1⋯AN−M−1A_{N-M} \cdots A_{N-1} A_0 A_1 \cdots A_{N-M-1}ANMAN1A0A1ANM1)(最后MMM个数循环移至最前面的MMM个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?

输入格式:

每个输入包含一个测试用例,第1行输入NNN1≤N≤1001\le N \le 1001N100)和MMM≥0\ge 00);第2行输入NNN个整数,之间用空格分隔。

输出格式:

在一行中输出循环右移MMM位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。

输入样例:

6 2
1 2 3 4 5 6

输出样例:

5 6 1 2 3 4
#include<stdio.h>
int main()
{
	int n,m;
	int i,j,a[100];
	
	scanf("%d %d",&n,&m);
	
	if(m>n)
	m=m%n;
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(i=n-m;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	for(j=0;j<=n-m-2;j++)
	{
		printf("%d ",a[j]);
	}
	printf("%d",a[n-m-1]);
} 

 

输出月份英文名

本题要求实现函数,可以返回一个给定月份的英文名称。

函数接口定义:

char *getmonth( int n );

函数getmonth应返回存储了n对应的月份英文名称的字符串头指针。如果传入的参数n不是一个代表月份的数字,则返回空指针NULL。

裁判测试程序样例:

#include <stdio.h>

char *getmonth( int n );

int main()
{
    int n;
    char *s;

    scanf("%d", &n);
    s = getmonth(n);
    if ( s==NULL ) printf("wrong input!\n");
    else printf("%s\n", s);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1:

5

输出样例1:

May

输入样例2:

15

输出样例2:

wrong input!
char *getmonth( int n )
{
    switch(n)
    {
    case 1:return "January";
    case 2:return "February";
    case 3:return "March";
    case 4:return "April";
    case 5:return "May";
    case 6:return "June";
    case 7:return "July";
    case 8:return "August";
    case 9:return "September";
    case 10:return "October";
    case 11:return "November";
    case 12:return "December";
    default:return NULL;
    }
}

 

用Strassen算法(分治)计算矩阵乘法及python实现(一)

前言:

设A和B都是n*n的矩阵,那么我们可以很容易通过一个简单的分治算法得到乘积C=A·B,以下是其伪代码,它将接收n*n矩阵A,B,并返回它们的乘积C:

SQUARE-MATRIX-MULLTIPLY(A,B)
n=A.rows
let C be a new n*n matrix
for i=1 to n
     for j=1 to n
         c[i][j]=0
         for k=1 to n
               c[i][j]=c[i][j]+a[i][k]*b[k][j]

return C

显然三重循环中每一重都要执行n布,因此其时间复杂度为O(n^3),而Strassen算法的时间复杂度为O(n^log7),显然Strassen算法更优。

Strassen算法的核心思想是通过常数次的额外的矩阵加法来减少递归的次数,如果你对递归有所了解,那么你应该明白这种代价确实能够减少渐进运行时间。下面来介绍一下Strassen算法的步骤

Strassen算法的步骤

为简单起见,当使用分治算法计算矩阵积C=A*B时,假定三个矩阵均为n*n矩阵,其中n为2的幂。我们做出这个假设是因为在每个分解步骤中,n*n矩阵都被划分为4个n/2*n/2的子矩阵,如果假定n是2的幂,则只要n>=2即可保证子矩阵规模n/2为整数。

Strassen算法一共4个步骤:

  1. 将输入矩阵A、B和输出矩阵C分解为n/2*n/2的子矩阵。采用下标计算方法,此步骤花费O(1)时间。
  2. 创建10个n/2*n/2的矩阵S1, S2, … , S10,每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间为O(n^2)。
  3. 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵,递归地计算7个矩阵积P1, P2, …, P7。每个矩阵Pi都是n/2*n/2的。
  4. 通过Pi矩阵的不同组合进行加减计算,计算出结果矩阵C的子矩阵C11, C12, C21, C22。花费时间O(n^2)。

以上即为Strassen算法的简略步骤,至于具体步骤,敬请期待 用Strassen算法(分治)计算矩阵乘法及python实现(二)。