优化C代码

假设我们有一组数字{1,2,3}并且我们希望尽可能少地轮换数字，其中的“转”的定义如下：优化C代码

在转弯时，你需要修复的元素之一的值是，和1

增加每隔数考虑到如。已经提到 - A = {1,2,3}，目标是均衡它们。我已经完成的是制定逻辑，即使用最小圈数的方法是在每一回合中选择最大数量。

迭代1：保持A [2] = 3。迭代结束时的阵列=> {2,3,3}

迭代2：保持A [2] = 3。阵列在迭代的结束=> {3,4,3}

迭代3：保持A [1] = 4。阵列在迭代的结束=> {4,4,4}

所以，采取匝数= 3

我写的代码如下：

#include<iostream> 
#include<stdio.h> 

int findMax(int *a,int n) 
{ 
    int i,max; 
    max=1; 
    for(i=2;i<=n;i++) 
    { 
     if(a[i]>a[max]) 
     { 
      max=i; 
     }  

    } 
    return max; 
} 

int equality(int *a,int n) 
{ 
    int i; 
    for(i=1;i<n;i++) 
    { 
     if(a[i]!=a[i+1]) return 0; 
    } 
    return 1; 
} 

int main() 
{ 
    int a[100],i,count,t,posn_max,n,ip=0; 
    scanf("%d",&t); 
    while(ip<t) 
    { 
     count=0; 
     scanf("%d",&n); 

     for(i=1;i<=n;i++) 
     { 
      scanf("%d",&a[i]); 
     } 
     while(equality(a,n)==0) 
     { 
      posn_max=findMax(a,n); 

      for(i=1;i<=n;i++) 
      { 
       if(i!=posn_max) 
       { 
        a[i]=a[i]+1; 
       } 
      } 
      count++; 

     } 
     printf("%d\n",count); 
     ip++; 
    } 
    return 0; 
}

这给我正确的答案，我需要好的。但我想进一步优化它。

我的时间限制为1.0秒。但法官网站告诉我我的代码需要1.01s。谁能帮我吗？

相比COUT/CIN，力图优化输入/输出部据我所看到的，我使用的scanf/printf语句。但还有什么我应该做得更好？

来源

2013-01-14 wave5459

'printf'不是很快......我怀疑它比'cout'快。 – leemes

同样存在缓冲区溢出。在循环i = n-1的最后一次运行中，所以a [i + 1]是一个[n]，它是n长度数组a的第n + 1个元素。 – SecurityMatt

您似乎认为数组从索引1开始。它们实际上从0开始。 –

在你的算法中，你正在增加所有数字的最大值。

如果你这样做的其他方式，降低了最大和离开的人数的休息，结果应该是相同的（但具有更少的内存/数组操作）！

为了使速度更快，您可以完全摆脱内存操作（如Ivaylo Strandjev也建议）：找到最小数量，并根据上面的想法（减少数字而不是增加），您知道多少减少了你要求将所有数字减少到最小数量。所以，找到最小值后，需要一个循环来计算转数。

把你的{1,2,3}

例如最小为匝数1
数量：（1-1）+（2-1）+（3-1）= 0 + 1 + 2 = 3

如果你真的很聪明，可以直接计算输入数字和跟踪当前最小数量的转数......试试吧！ ;）

来源

2013-01-14 15:59:16 Veger

{0,2,3}呢？ – duedl0r

仍然有效：（0-0）+（2-0）+（3-0）= 5转。原始算法：{1,3,3}，{2,4,3}，{3,4,4}，{4,5,4}，{5,5,5} = 5圈 – Veger

aehem ..right .. :) – duedl0r

您只关心计数而不关心您需要执行的实际操作。所以不是一步一步的执行这些动作，而是试图找到一种方法来计数移动的数量没有执行他们。无论你优化它的程度如何，你写的代码都不会在时间限制内传递。你所做的最大元素观察将帮助你一路走来。

来源

2013-01-14 15:51:42

1）尝试展开循环 2）您可以使用SIMD指令吗？这真的会加快代码的速度

来源

2013-01-14 16:02:04

除了其他的评论，如果我得到这个权利，你的代码只是有点太慢，这里有两个优化，这应该可以帮助你。首先，可以将equality（）和findMax（）组合起来，只扫描一次数组，而不是当前最差的情况（两次）。其次，您可以将“增加”循环分为两部分（低于和高于最大位置）。这将消除检查循环中位置的工作。

来源

2013-01-14 16:06:04

我会printf在一个单独的线程，因为它是一个I/O操作，并且比计算速度慢得多。

它也不要求复杂的管理，例如生产者 - 消费者队列，因为你只传递从0到最后count的有序数字。

这里是伪代码：

volatile int m_count = 0; 
    volatile bool isExit = false; 

    void ParallelPrint() 
    { 
     int currCount = 0; 

     while (!isExit) 
     { 
      while (currCount < m_count) 
      { 
       currCount++; 
       printf("%d\n", currCount); 
      } 

      Sleep(0); // just content switch 
     } 
    }

打开scanf("%d",&t);（我猜这个初始化时间不计算在内），并从Main()返回前关闭由isExit = true;线程之前线程。

来源

2013-01-14 16:45:11

回答

相关问题