首页 > 试题广场 >

一个长度为n的数组a[0],a[1],...,a[n-1]。

[问答题]
一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素,即a[0]变为a[1]到a[n-1]的积 a[1]变为a[0]和a[2]到a[n-1]的积,...,a[n-1]为a[0]到a[n-2]的积。
程序要求:要求具有线性复杂度,不能使用除法运算符。

/**
策略:把乘积分为前半部分*后半部分
*/
#include<iostream>
using namespace std;

void input(int* a,int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
}
void printResult(long long int * res,int n)
{
    int i;
    cout<<res[0];
    for(i=1;i<n;i++)
    {
        cout<<" "<<res[i];
    }
    cout<<endl;
}

void getResult(int *a,int n)
{
    long long int * res =new long long int[n];
    res[0]=1;
    int i;
    for(i=1;i<n;i++)
    {
        res[0]=res[0]*a[i-1];
        res[i]=res[0]; //前半部分乘积 
    }
    res[0]=1;
    for(i=n-2;i>0;i--)
    {
        res[0]=res[0]*a[i+1]; //后半部分乘积 
        res[i]=res[i]*res[0]; // 结果 
    }
    res[0]=res[0]*a[1];
    printResult(res,n);
    delete []res;
}

int main()
{
    int n;
    cin>>n;
    int *a= new int[n];
    input(a,n);
    getResult(a,n);
    delete []a;
    return 0;
}












编辑于 2019-06-11 15:14:35 回复(0)
#include<stdio.h>
#define N 4
int main(void)
{
 int a[N]={1,2,3,4};
 int b[N];
 int i,j;
 for(i=0;i<N;i++)
  b[i]=1;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   if(i!=j)
    b[i]=b[i]*a[j];
 for(i=0;i<N;i++)
  a[i]=b[i];
 for(i=0;i<N;i++)
  printf("%4d",a[i]);
 printf("\n");
 return 0;
}
发表于 2019-06-10 15:09:24 回复(0)