1、求A的绝对值。

答：

算法如下：

int A;

if(A<0) A=-A;

return A;

流程图如截图：

 

2、水仙花的算法及流程图

 int gw,sw,bw;               //gw,bw,sw分别代表十位，百位，各位

    int i;                      //i为循环变量，控制循环次数（范围）

    for(i=100;i<1000;i++)

    {

        gw=i%10;              

        sw=i/10%10;

        bw=i/100;

        if(i==gw*gw*gw+sw*sw*sw+bw*bw*bw)

        {

            return i

        }

    }

 

二算法分析题目

1,因为 sum=0; //执行1次

for(i=1;i<=n;i++) //执行n+1次

for(j=1;j<=n;j++) //执行n*(n+1)次

sum++； //执行n*n

所以时间复杂度T(n)=1+n+1+n*(n+1)+n*n=2n^2+n+2=O(n^2)

 

2,因为 for(i=1;i<=n;i+=2) //执行了n/2次

所以时间复杂度T(n)=n/2=O(n)

 

3,因为 i=1; //执行了1次

while(i<=n) //执行了n+1次

i=i*2; //执行了n次

所以时间复杂度T(n)=1+n+1+n=2n+1=O(n)

4,

因为 int i=1,k=100; //执行了1次

while(i<n) //执行了n次

{

k=k+1; //执行了n次

i+i+2; //执行了n次

}

所以时间复杂度T(n)=1+n+n+n=3n+1=O(n)

 

5,因为 x=n; //n>1 //执行了1次

y=0; //执行了1次

while((x>(y+1)*)(y+1)) //执行了log2^n+1次

y=y+1; //执行了log2^n次

所以时间复杂度T(n)=1+1+log2^n+1+log2^n=2log2^n+3=O(logn)

 

三 算法设计题。

1.输入一个正整数 从高到低输出

int x;

if( x >= 10)

    {

        x=x/10;

    }

       x=x % 10;

return x;

 

2. 输入一个数，同时被3和5整除，是输入Yes,否则为No

 

int n;

string result;

if(n%3==0&&n%5==0)

{

result="Yes";

}

else

{

result="No";;

}

return result;

四 冒泡算法的时间复杂度及空间复杂度

//打印数组元素

 void print_array(int *array, int length)

 {

     int index = 0;

     printf("array:\n");

     for(; index < length; index++){

         printf(" %d,", *(array+index));

     }   

     printf("\n\n");

 }

 

 void bubbleSort(int array[], int length)

 {

     int i, j, tmp;

     

     if (1 >= length) return;// 判断参数条件

 

     for (i = length-1; i > 0; i--){//外循环，循环每个元素

         for (j = 0; j < i; j++){  // 内循环，

             if (array[j] > array[j+1]){// 交换相邻的两个元素

                 tmp        = array[j];

                 array[j]   = array[j+1];

                 array[j+1] = tmp;

             }   

         }   

     }   

 }

 

 这个时间复杂度还是很好计算的：外循环和内循环以及判断和交换元素的时间开销；

 

       最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] /  2；所以最优的情况时间复杂度为：O( n^2 )；

 

       最差的情况也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[ 3n(n-1) ] / 2；（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；所以最差的情况下时间复杂度为：O( n^2 )；

 

        综上所述：

 

       最优的时间复杂度为：O( n^2 ) ；有的说 O(n)，下面会分析这种情况；

 

       最差的时间复杂度为：O( n^2 )；

 

       平均的时间复杂度为：O( n^2 )；

空间复杂度

      空间复杂度就是在交换元素时那个临时变量所占的内存空间；

     最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；

     最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；

     平均的空间复杂度为：O(1)；

 

 

1.选择排序：不稳定，时间复杂度?O(n^2)? 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。??

 2.插入排序：稳定，时间复杂度?O(n^2)? 插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]?又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤?L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j]?≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。?

3.冒泡排序：稳定，时间复杂度?O(n^2)? 冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。?? 

4.堆排序：不稳定，时间复杂度?O(nlog?n)? 堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。??

 5.归并排序：稳定，时间复杂度?O(nlog?n)?

设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。??

 6.快速排序：不稳定，时间复杂度?最理想?O(nlogn)?最差时间O(n^2)?快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。? 

7.希尔排序：不稳定，时间复杂度?平均时间?O(nlogn)?最差时间O(n^s)?1<s<2? 在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为?增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。