hiho一下第77周《Koch Snowflake》题目分析

0
2

题目大意

给定一个三角形，每经过一次迭代，每一条边变成4条小一点的边。告诉你迭代的次数，以及边的编号，求该条边是第几次迭代出现的边。

解题思路

本题是一道数学题，用找规律的方法即可解决。

我们先来观察一下一条边在两次迭代之前的变化情况：

pic1

其中黄线为我们选中的一条边，我们并不知道它是第几次迭代产生的边。蓝线是第n次迭代后产生的新边，因此其代数为n。

假设迭代前的边为原图形中第i条边，那么迭代后对应的新图形中第4(i-1)+1 .. 4(i-1)+4这四条边。

在新的四条边中，我们可以知道4(i-1)+2和_4(i-1)+3_这两条边一定是当前迭代产生新边。同时我们可以根据其序号，算出原来的i。

由此我们可以得到结论，对于第n次迭代后的第k条边，若：

  • k mod 4 == 2或3：则该边一定是第n次迭代产生的新边；
  • k mod 4 == 0或1：则该边不是第n次迭代产生的新边，且该边在第n-1次迭代中对应的是第ceil(k/4)条边。(ceil为上取整函数)

利用这个性质，对于给定的k和n，我们先判定第k条边是否是第n次迭代产生的新边。若是，则直接返回n；否则我们根据第二条性质，计算出的新的k' = ceil(k/4),n' = n - 1，再次代入进行计算。

我们可以写出这个递归的程序：

calc(k, n):
    If (n == 0) Then
        Return 0;   // 若n = 0时，该边一定属于初始图形
    End If
    If (k mod 4 == 2 or k mod 4 == 3) Then
        Return n;
    End If
    Return calc(ceil(k/4), n - 1);

得到了该函数，本题也就迎刃而解了。

9 answer(s)

0

include "iostream"

include "cmath"

using namespace std;

int calc(int k, int n) { if(k == 0) return 0; else if(k%4==2 || k%4==3) return n; else return calc(ceil(k/4), n-1); }

int main() { int k, n; cin >> k; cin >> n; cout << calc(k, n) << endl; return 0; }

0 
 #include <iostream>
using namespace std;   
int main()
    {
        int n;
        cin >>n;
        while(n--)
        {
            int id, it;
            cin >> id >> it;
            while(it)
            {
                if(id%4 == 2 || id%4 == 3) break;
                id = id/4 + id%4;
                --it;
            }
            cout << it << endl;
        }
        return 0;
    }
0

include

using namespace std; int cal(int k,int n) { if(n==0) return 0; else if(k%4==2||k%4==3) return n; else return cal(k/4+1,n-1); } int main() { int m; cin>>m; int n[m],k[m]; for( int i=0;i>k[i]>>n[i]; for(int i=0;i

0

include

using namespace std;

int getGeneration(int pID,int pTime) { if (pTime == 0) return 0; int pID_last = pID / 4 + 1; if (pID % 4 == 0) pID_last--; int lastGeneration = getGeneration(pID_last, pTime - 1); if (pID % 4 == 0 || pID % 4 == 1) { return lastGeneration; } else { return pTime; } }

int main() { unsigned int total_num; cin >> total_num; for (unsigned int x = 0; x < total_num;x++) { unsigned int i, n; cin >> i >> n; cout << getGeneration(i, n)<

0

include

include

include

using namespace std; int cal(int k,int n) { if ((k%4==2)||(k%4==3)||(!n)) return n; else return cal(ceil(k/4),n-1); } int main() { int kase,n,k; while (scanf("%d",&kase)==1) { while (kase--) { scanf("%d%d",&k,&n); printf("%d\n",cal(k,n)); } } return 0; }

这个哪里出问题了

0

public static int calc(int k, int n) { if (n == 0) return 0;

int r = k % 4;
if (r == 2 || r == 3)
    return n;

if (r == 0)
    return calc(k / 4, n - 1);

return calc(1 + k / 4, n - 1);

}

public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); for (int i = 0; i < T; i++) { int k = scanner.nextInt(); int n = scanner.nextInt(); System.out.println(calc(k, n)); }

scanner.close();

} }

0

//package smartjune;

import java.util.Scanner;

public class Main {

/*
 * KochSnowflake
 */
public static int calc(int k, int n) {
    if (n == 0)
        return 0;

    int r = k % 4;
    if (r == 2 || r == 3)
        return n;

    if (r == 0)
        return calc(k / 4, n - 1);

    return calc(1 + k / 4, n - 1);
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int T = scanner.nextInt();
    for (int i = 0; i < T; i++) {
        int k = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(calc(k, n));
    }

    scanner.close();
}

}

0 
int cal(int i,int k){
    while(i%4==1||i%4==0){
            if(i==1) return 0;
            i=(i+3)/4;
            //i=(int)ceil(i/4);
            k--;
}
    return k;
}

int main(){
    int i,k,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&i,&k);
        printf("%d\n",cal(i,k));
    }
}

请问这段代码的问题在哪

  • 有个数据错了，i > 3*n^4了， 已经修正。

  • 添加评论
  • ✖reply
0 
#include <iostream>
#include <stdio.h>

using namespace std;
/* 递归*/
unsigned int calc(unsigned int k, unsigned int n) 
{
        if( n == 0) 
                return 0;

        if( k%4 == 2 || k%4 == 3)
                return n;

        return calc( (k+3)/4, n-1 ); 
}

/* 非递归 */
unsigned int calc2(unsigned int k, unsigned int n)
{
        unsigned int kk = k, nn = n;

        while(1)
        {
                if( nn == 0)
                        return 0;

                if( kk%4 == 2 || kk%4 == 3)
                        return nn;

                kk = (kk+3)/4;
                nn--;
        }
}


int main()
{
        unsigned int k,n;
        k = 6;
        n = 3;
        printf( "%d,%d\n", calc(k,n), calc2(k,n) );
       return 0;
}

  • 你可以去 http://hihocoder.com/contest/hiho77/problems 提交一下。不过要先根据题目描述把k和n改成从stdin读入，并且能处理多组数据。

  • 我刚提交为什么有罚时

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲